|Location :||Gamble project-team|
|INRIA - Nancy Grand Est, LORIA, FRANCE|
Duration: 3 years
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 very specific hyperbolic surfaces [IT]. 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
French is not compulsory. English is required.