PhD topic: Computing periodic Delaunay triangulations


Supervisor and Location
Monique Teillaud
Gamble group, INRIA Nancy - Grand Est, LORIA

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 was limited to manipulations of geometric elements in the Euclidean spaces Rd.
More recently, motivated by needs in other application domains, algorithms were proposed to compute triangulations in d-dimensional closed Euclidean manifolds [1,2].
In practice, a software package computing Delaunay triangulations in the special case of the flat torus with cubic domain was distributed in the CGAL library [3]. Such triangulations can equivalently be seen as periodic triangulations, where the periodicity domain is a cube (see the video). The software package was successfully used in several fields, including astronomy [4].

Handling other types of periodicity in practice is necessary to extend the applicability of previous work to a wider range of fields.
The objectives of the PhD consist in extending previous work in both theoretical and practical directions:

A special care will be put both on the mathematical soundness of the proposed solutions and on the quality of the C++ implementations, targeting a longer-term integration into CGAL.

[1] Manuel Caroli and Monique Teillaud. Delaunay triangulations of closed Euclidean d-orbifolds. Discrete & Computational Geometry, 55(4):827-853, 2016. [WWW]
[2] Manuel Caroli. Triangulating Point Sets in Orbit Spaces. PhD thesis, Université de Nice Sophia Antipolis, 2010. [WWW]
[3] Manuel Caroli and Monique Teillaud. 3D Periodic Triangulations. In CGAL Editorial Board, editor, CGAL User and Reference Manual. [WWW]
[4] Johan Hidding, Rien van de Weygaert, Gert Vegter, Bernard J.T. Jones, and Monique Teillaud. Video: The sticky Geometry of the Cosmic Web. In Proceedings 28th Annual Symposium on Computational Geometry, pages 421-422, 2012. [WWW]

Skills and profile
Required qualification: Master in mathematics or computer science

Required skills and knowledge:

Optional knowledge:
Last modified: Thu Apr 6 15:55:30 CEST 2017