Bachelor internship: Heuristics for Computing Delaunay Triangulations on Flat Tori

Supervision and Contact: Vincent Despré and Monique Teillaud
Location: Gamble group, INRIA Nancy - Grand Est, LORIA

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.

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²), 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.

Goal of the internship

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.

Required skills

- Algorithms design and analysis
- C++
- Basics in maths (vector spaces, groups, topology)

References

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