More Spaces for Computational Geometry

Geometric problems are central in many areas of science and engineering. Computational geometry, the study of combinatorial and algorithmic problems in a geometric setting, has tremendous practical applications in areas such as computer graphics, computer vision and imaging, scientific visualization, geographic information systems,...
Traditionally, the scope of computational geometry research has been limited to manipulation of geometric elements in the Euclidean space R^d.

Due to the recent emergence of standardized software libraries, in particular the Computational Geometry Algorithms Library CGAL, developed in the framework of an Open Source Project, the so-far mostly theoretical results developed in computational geometry are being used and extended for practical use like never before.
To fulfill the promise of applicability of these results for the benefit of both researchers in academia and of the industry, and to expand the scope of some initial efforts, it is important to extend the traditional focus on R^d to encompass other geometric spaces. Impact is expected in various fields like simulation of fluid dynamics, chemical engineering, astronomy, cristallography, computer graphics, computer vision...

[ Related publications ]

Related Events
Structures on Surfaces, CIRM, Marseille, May 2 - 6, 2022
Astonishing workshop, LORIA, Nancy, September 25-26, 2017
Geometric Aspects of Materials Science, Brisbane, Australia, July 4-5, 2017
Workshop on Computational geometry in non-Euclidean spaces, INRIA, LORIA, Nancy, August 26--28, 2015
Workshop on Geometric Structures with Symmetry and Periodicity, Kyoto University, Japan, June 8-9, 2014
OrbiCG/Triangles Workshop on Computational Geometry, INRIA Sophia Antipolis - Méditerranée, 8 - 10 Dec 2010
Subdivide and Tile: Triangulating spaces for understanding the world (program), Lorentz Center, Leiden, The Netherlands, 16 - 20 Nov 2009
CGAL Prospective Workshop on Geometric Computing in Periodic Spaces, INRIA Sophia Antipolis - Méditerranée, 20 October 2008

This work has been partially supported by
SoS, ANR-FNR project (2018-2023)
Astonishing, INRIA Associate Team (2016-2019)
P3M3, INRIA Fasttrack Technological Development Action (2017)
OrbiCGAL, INRIA Technological Development Action (2013-2015)
OrbiCG, INRIA Associate Team (2009-2011)
Triangles, ANR project (2007-2010)

*Delaunay Triangulations of Closed Euclidean Manifolds*
(image by Manuel Caroli - larger version)	Flat torus with square fundamental domain [ESA'09] Software package [CGAL'09] Used e.g., by researchers in astronomy [astro, orbicg]. See also the video [The Sticky Geometry of the Cosmic Web]. More users: search for "periodic" in this page. Flat torus with general fundamental domain [ESA'20 (best paper)] CGAL package in progress Closed d-dimensional flat orbifolds [SoCG'11, DCG'16] See also Manuel Caroli's PhD thesis
*Periodic Meshes*
[poster, IMR'14] Software package [CGAL'18], see also here. The package has users in materials engineering and nano-structures.	(internship of Mikhail Bogdanov)
*Delaunay Complexes in Hyperbolic Spaces*
	[JoCG'14, SoCG'13] The space of circles gives some mathematical background for this work. Software package [CGAL'19].
*Delaunay Triangulations of Closed Hyperbolic Surfaces*
First results [SoCG'16] Bolza surface (genus 2) Cycles. See also Length spectrum. Implementation [SoCG'17] Software package [CGAL'19] The work is expected to have applications in various fields, see e.g., [GFF'11 , CF'09, FCF'10, RFG'10] Generalized Bolza surfaces (genus g) [JoCG'22] See also Iordan Iordanov's PhD thesis. General closed hyperbolic surfaces Flip graph [SoCG'20] - Experiments [Preprint'21-22] Finite representation in the Poincaré disk [Preprint'21] Computing a Dirichlet domain [Preprint'22]	(internship of Mathieu Schmitt) [RR 8179]
*Delaunay Triangulations of the Sphere*
	[SEA'10] Software package [CGAL'21] (work started during the internship of Olivier Rouiller and improved during the internship of Claudia Werner)
*Triangulations of the Projective Plane*
[MACIS'07] (work done during the internship of Mridul Aanjaneya)

Monique Teillaud