Delaunay triangulations on orientable surfaces of low genus

Mikhail Bogdanov 1 Monique Teillaud 2 Gert Vegter 3
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
2 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : Earlier work on Delaunay triangulation of point sets on the 2D flat torus, which is locally isometric to the Euclidean plane, was based on lifting the point set to a locally isometric 9-sheeted covering space of the torus. Under mild conditions the Delaunay triangulation of the lifted point set, consisting of 9 copies of the input set, projects to the Delaunay triangulation of the input set. We improve and generalize this work. First we present a new construction based on an 8-sheeted covering space, which shows that eight copies suffice for the standard flat torus. Then we generalize this construction to the context of compact orientable surfaces of higher genus, which are locally isometric to the hyperbolic plane. We investigate more thoroughly the Bolza surface, homeomorphic to a sphere with two handles, both because it is the hyperbolic surface with lowest genus, and because triangulations on the Bolza surface have applications in various fields such as neuromathematics and cosmological models. While the general properties (existence results of appropriate covering spaces) show similarities with the results for the flat case, explicit constructions and their proofs are much more complex, even in the case of the apparently simple Bolza surface. One of the main reasons is the fact that two hyperbolic translations do not commute in general. To the best of our knowledge, the results in this paper are the first ones of this kind. The interest of our contribution lies not only in the results, but most of all in the construction of covering spaces itself and the study of their properties.
Type de document :
Communication dans un congrès
International Symposium on Computational Geometry, Jun 2016, Boston, United States. pp.20:1--20:15, 2016, <http://socg2016.cs.tufts.edu>. <10.4230/LIPIcs.SoCG.2016.20>
Liste complète des métadonnées



https://hal.inria.fr/hal-01276386
Contributeur : Monique Teillaud <>
Soumis le : vendredi 1 avril 2016 - 16:59:47
Dernière modification le : samedi 18 février 2017 - 01:14:34
Document(s) archivé(s) le : lundi 14 novembre 2016 - 13:02:01

Identifiants

Citation

Mikhail Bogdanov, Monique Teillaud, Gert Vegter. Delaunay triangulations on orientable surfaces of low genus. International Symposium on Computational Geometry, Jun 2016, Boston, United States. pp.20:1--20:15, 2016, <http://socg2016.cs.tufts.edu>. <10.4230/LIPIcs.SoCG.2016.20>. <hal-01276386>

Partager

Métriques

Consultations de
la notice

311

Téléchargements du document

144