[PhD topic] A toolbox for hyperbolic surfaces
Context and motivation
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. Traditionally, the scope of computational geometry has been limited to algorithms on data in the Euclidean space.
However, some results in computer science used combinatorial hyperbolic structures [SST,DL]. Also, hyperbolic surfaces are natural and appear in various fields in physics and material sciences. For instance, the triply periodic minimal surfaces of R3 are hyperbolic.
We have already obtained results about the computation of Delaunay triangulations in hyperbolic spaces [BDT] and on hyperbolic surfaces [IT,DST]. The need of a geometric toolbox for hyperbolic surfaces has become critical to tackle more general hyperbolic surfaces. Some combinatorial constructions on such surfaces have been proposed from a mathematical point of view [Bus]; however the algorithmic and practical properties have hardly been studied.
The purpose of this PhD is to explore the geometry of hyperbolic surfaces and provide such a geometric toolbox.
Two main discrete structures have been proposed to describe hyperbolic surfaces: Fenchel-Nielsen coordinates and fundamental polygon with side gluings. These representations are not unique, which leads to research question like: how to compute a good pants decomposition? or how to compute a fundamental domain that is a Voronoi cell? Also, elementary queries associated to the underlying surface can be studied in both situations. A typical question that is both extremely useful and a deep research question is: how to calculate the distance between two given points on an hyperbolic surface?
Many other interesting questions may be considered, so, the candidate will have the opportunity to choose between different possible directions. In each case, the goal will be to present an algorithm, analyze it, and implement it. Considering the potential applications and targeted users, SageMath seems to be a good option for implementations.
This PhD thesis involves knowledge from both
- mathematics (in particular: low-dimensional topology and geometry)
- and computer science (in particular: algorithms, graph theory, and C++/Python).
Candidates should have a strong expertise in one of those fields and a real interest for the other one.
French is not compulsory. English is required.
[BDT] Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud. Hyperbolic Delaunay complexes and Voronoi diagrams made practical. Journal of Computational Geometry. 5(2014)
[Bus] Peter Buser. Geometry and spectra of compact Riemann surfaces. Springer Science & Business Media, 2010.
[DL] Vincent Despré and Francis Lazarus. Computing the geometric intersection number of curves. 33rd International Symposium on Computational Geometry (SoCG 2017).
[DST] Vincent Despré and Jean-Marc Schlenker and Monique Teillaud. Flipping Geometric Triangulations on Hyperbolic Surfaces. 36th Symposium on Computational Geometry (SoCG 2020). To appear.
[IT] Iordan Iordanov and Monique Teillaud. Implementing Delaunay triangulations of the Bolza surface. 33rd International Symposium on Computational Geometry (SoCG 2017).
[STT] Daniel D. Sleator, Robert E. Tarjan, and William P. Thurston. Rotation distance, triangulations, and hyperbolic geometry. Journal of the American Mathematical Society. 1(1988).