Covering spaces and Delaunay triangulations of the 2D flat torus

Mikhail Bogdanov (1) , Monique Teillaud (1) , Gert Vegter (2)

1 GEOMETRICA - Geometric computing
2 Bernoulli Institute for Mathematics and Computer Science and Artificial Intelligence

A previous algorithm was computing the Delaunay triangulation of the flat torus, by using a 9-sheeted covering space. We propose a modification of the algorithm using only a 8-sheeted covering space, which allows to work with 8 periodic copies of the input points instead of 9. The main interest of our contribution is not only this result, but most of all the method itself: this new construction of covering spaces generalizes to Delaunay triangulations of surfaces of higher genus.

Domaines: Géométrie algorithmique [cs.CG]

Mikhail Bogdanov, Monique Teillaud, Gert Vegter. Covering spaces and Delaunay triangulations of the 2D flat torus. 28th European Workshop on Computational Geometry, Mar 2012, Assisi, Italy. ⟨hal-01109626⟩