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

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

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

We are interested by the generalization of the Delaunay triangulations
on 2D flat tori [CT]. A 2D flat torus is the quotient of the Euclidean plane
under the action of a group generated by two non-collinear
translations [MT]. Thus, each point of a set P on the flat torus
corresponds to a lattice in the Euclidean plane. On flat tori, 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 and can hopefully be improved by using a good
heuristic for the order of the flips.

Propose heuristics to optimize the flip algorithm to compute Delaunay triangulations of flat tori.

The problem may be attacked in several ways: the student may either do a lot of experiments and benchmarking or spend more time on theoretical aspects and propose more intricate heuristics (using volume of simplexes for instance [STT]) and give an actual complexity proof.

- Algorithms design and analysis

- C++

- Basics in maths (vector spaces, groups, topology)

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

[CT] M. Caroli and M. Teillaud.
Delaunay Triangulations of Point Sets in Closed Euclidean d-orbifolds.
Discrete & Computational Geometry, 55(4):827-853, 2016.

[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.

[STT] D. Sleator, R. Tarjan and W. Thurston.
Rotation Distance, Triangulations, and Hyperbolic Geometry.
Journal of the AMS, 1986.

Last modified: Sat Sep 12 10:13:55 CEST 2020