# Master internship: Flipping triangulations of hyperbolic surfaces

**Supervision and Contact:**
Vincent Despré
and
Monique Teillaud

**Location:**
Gamble group, INRIA Nancy - Grand Est,
LORIA

**The work may extend to a PhD on a related topic.**

### Context

In the Euclidean plane, the Delaunay triangulation of a set of n points
P is the unique (when P is non-degenerate) triangulation with vertex
set P for which the circumdisk of each triangle does not contain any
point of P in its interior. It has many applications and has
been extensively studied [BCKO].

When a general (non-Delaunay) triangulation is given a sequence of
edge flips allows to compute the Delaunay triangulation.

The worst-case complexity of that sequence is O(n^{2}). Moreover, that
bound is tight [HNU], so, there is no way to order the flips to
improve the worst-case complexity.
We are interested by the generalization of the Delaunay triangulations
on surfaces of genus > 1. Such a surface is a hyperbolic surface, which
can be seen as the quotient of the hyperbolic plane under the action
of a discrete group of hyperbolic isometries [MT]. The flip algorithm has a
complexity O(f(T).n^{2}), where f(T) is an explicit measure of the
quality of the input triangulation T [DST]. This measure f(T) is not
proven to be tight.

### Goal of the internship

The twofold objectives are to
propose optimizations to the flip algorihms in theory as well as in
practice. To this aim, the student will first need to deeply
understand the mathematical aspects of the algorithm on hyperbolic
surfaces. (S)he will study the possibility to propose better measures
of the quality of the input triangulation. (S)he will also implement
the algorithm in C++ and propose heuristic improvements.

### Required skills

- Groups, topology, geometry,

- Algorithms design and analysis,

- Basic skills in C++.

### References

[BCKO] M. de Berg, O. Cheong, M. van Kreveld and M. Overmars.
Computational Geometry: Algorithms and Applications.
Springer-Verlag, 2008.

[DST] Vincent Despré, Jean-Marc Schlenker, and Monique Teillaud.
Flipping Geometric Triangulations on Surfaces.
36th Symposium on Computational Geometry, 2020.

[HNU] F. Hurtado, M. Noy, and J. Urrutia.
Flipping edges in triangulations.
Discrete & Computational Geometry, 22(3):333-346, 1999.

[MT] B. Mohar and C. Thomassen.
Graphs on Surfaces.
Johns Hopkins University Press, 2001.

Last modified: Mon Oct 26 16:20:47 CET 2020