PhD topic: Computing periodic Delaunay triangulations

• Deadline: April 30, 2017
• You can apply for two calls in parallel:
  • INRIA: Information and application forms
  • UL: Topic (look at both French and English versions) then follow link "Candidater" at the bottom of the page
• Please also contact the supervisor.

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

Topic
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 R^d.
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:

• Propose data structures and algorithms to compute Delaunay triangulations of non-compact flat manifolds.
• Make previous work [1] practical also for non-cubic periodicity domains.
• Implement the algorithms in 3D.

References
[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:

• Background on Algorithmics and Computational Geometry (Delaunay triangulations,...)
• Taste for mathematics
• C++
• Good writing skills
• Good level in English (French is welcome but not required)

• Group theory, in particular finitely presented groups
• CGAL