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 Rd.
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 Rd 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 Flat torus with general fundamental domain
  • [ESA'20 (best paper)]
  • CGAL package in progress
Closed d-dimensional flat orbifolds

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

Delaunay Triangulations of Closed Hyperbolic Surfaces

Bolza surface (genus 2)

Generalized Bolza surfaces (genus g)

General closed hyperbolic surfaces

(internship of Mathieu Schmitt) [RR 8179]
Delaunay Triangulations of the Sphere
(work started during the internship of Olivier Rouiller and improved during the internship of Claudia Werner)

Triangulations of the Projective Plane

(work done during the internship of Mridul Aanjaneya)

Monique Teillaud