Supervision and Contact:
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.
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).n2), 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.
[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.