Delaunay triangulations on orientable surfaces of low genus

Mikhail Bogdanov, Monique Teillaud, Gert Vegter

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)

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 [28, 20, 12, 11]. 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 [32, 3, 15]. 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.

Original languageEnglish
Title of host publication32nd International Symposium on Computational Geometry, SoCG 2016
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages20.1-20.17
Volume51
ISBN (Electronic)9783959770095
DOIs
Publication statusPublished - 1-Jun-2016
Event32nd International Symposium on Computational Geometry, SoCG 2016 - Boston, United States
Duration: 14-Jun-201617-Jun-2016

Conference

Conference32nd International Symposium on Computational Geometry, SoCG 2016
Country/TerritoryUnited States
CityBoston
Period14/06/201617/06/2016

Keywords

  • Covering spaces
  • Finitely presented groups
  • Fuchsian groups
  • Hyperbolic surfaces
  • Systole

Cite this