Astonishing

Scientific Objectives

We aim at studying various structures and algorithms in other spaces than R^d, from a computational geometry viewpoint. Proposing algorithms operating in such spaces requires a prior deep study of the mathematical properties of the objects considered, which raises new fundamental and difficult questions that we want to tackle.

Methodology. A key characteristic of the project is its interdisciplinarity: it gathers approaches, knowledge, and tools in mathematics and computer science.
A mathematical study of the considered objects will be performed, together with the design of algorithms when applicable. Algorithms will be analyzed both in theory and in practice after prototype implementations. In the long term, implementations should be improved whenever it makes sense to target longer-term integrations into CGAL, in order to disseminate our results to end-users.

Challenges. The global difficulty of this project is intrinsic to the differences between the classical Euclidean spaces and the spaces that we consider (to spot only one concrete example: translations in the hyperbolic plane do not commute). This prevents known algorithms of computational geometry from naturally extending to other spaces. The mathematical difficulties are real and new ideas will be necessary. The challenge is to provide new mathematical foundations for computational geometry, in order to allow the emergence of algorithms that will be both efficient in theory and effective in practice.

Workshops

• 2017: September 25 - 26

News

Visits to/from Groningen are partially supported by the University of Groningen.
Visits to/from Luxembourg are partially supported by the University of Luxembourg. Since January 2018, those visits, as well as visits between INRIA and LIGM, fall under the umbrella of the project SoS, co-funded by ANR and FNR.

Publications and Presentations

• Mikhail Bogdanov, Monique Teillaud, and Gert Vegter. Delaunay triangulations on orientable surfaces of low genus. Proceedings of SoCG'16, the Thirty-second International Symposium on Computational Geometry, pages 20:1-20:15, Boston, June 14-18, 2016.
• Iordan Iordanov and Monique Teillaud. Implementing Delaunay Triangulations of the Bolza Surface. Proceedings of SoCG'17, the Thirty-third International Symposium on Computational Geometry, pages 44:1--44:15, Brisbane, July 4-7, 2017.
• Iordan Iordanov and Monique Teillaud. 2D periodic hyperbolic Delaunay triangulations, software prototype, July 2017. The software was submitted for integration into CGAL in June 2018.
• Matthijs Ebbens. Delaunay triangulations on hyperbolic surfaces, Master thesis, U. Groningen, August 21, 2017.
• Vincent Despré, Olivier Devillers, Hugo Parlier, and Jean-Marc Schlenker. Delaunay triangulations of points on circles. Preprint, April 2018.
• Matthijs Ebbens. Systole of regular hyperbolic surfaces with an application to Delaunay triangulations. Joint work with Iordan Iordanov, Monique Teillaud, and Gert Vegter. Curves and Surfaces, June 27 - July 4, 2018.
• Iordan Iordanov. Delaunay triangulations of regular hyperbolic surfaces. Joint work with Matthijs Ebbens, Monique Teillaud, and Gert Vegter. Curves and Surfaces, June 27 - July 4, 2018.
• Iordan Iordanov and Monique Teillaud. 2D periodic hyperbolic Delaunay triangulations. CGAL 4.14 User and Reference Manual. CGAL Editorial Board. March 2019.
• Iordan Iordanov. Video produced by the CGAL package and illustrating the trajectory of a particle moving freely on the Bolza surface.
• Iordan Iordanov. Delaunay triangulations of a family of symmetric hyperbolic surfaces in practice. PhD thesis, U. Lorraine, March 12, 2019.
• Matthijs Ebbens, Iordan Iordanov, Monique Teillaud, and Gert Vegter. Delaunay triangulations of symmetric hyperbolic surfaces. EuroCG'19 - 35th European Workshop on Computational Geometry. March 18 - 20, 2019.