Skip to Main content Skip to Navigation

Delaunay triangulations and cycles on closed hyperbolic surfaces

Mikhail Bogdanov 1 Monique Teillaud 1 
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : This work is motivated by applications of periodic Delaunay triangulations in the Poincaré disk conformal model of the hyperbolic plane H^2. A periodic triangulation is defined by an infinite point set that is the image of a finite point set by a (non commutative) discrete group G generated by hyperbolic translations, such that the hyperbolic area of a Dirichlet region is finite (i.e., a cocompact Fuchsian group acting on H^2 without fixed points). We consider the projection of such a Delaunay triangulation onto the closed orientable hyperbolic surface M = H^2/G. The graph of its edges may have cycles of length one or two. We prove that there always exists a finite-sheeted covering space of M in which there is no cycle of length <= 2. We then focus on the group defining the Bolza surface (homeomorphic to a torus having two handles), and we explicitly construct a sequence of subgroups of finite index allowing us to exhibit a covering space of the Bolza surface in which, for any input point set, there is no cycle of length one, and another covering space in which there is no cycle of length two. We also exhibit a small point set such that the projection of the Delaunay triangulation on the Bolza surface for any superset has no cycle of length <=2. The work uses mathematical proofs, algorithmic constructions, and implementation.
Document type :
Complete list of metadata

Cited literature [37 references]  Display  Hide  Download
Contributor : Monique Teillaud Connect in order to contact the contributor
Submitted on : Sunday, April 13, 2014 - 4:20:49 PM
Last modification on : Thursday, January 20, 2022 - 5:30:33 PM
Long-term archiving on: : Sunday, July 13, 2014 - 10:40:51 AM


Files produced by the author(s)


  • HAL Id : hal-00921157, version 2



Mikhail Bogdanov, Monique Teillaud. Delaunay triangulations and cycles on closed hyperbolic surfaces. [Research Report] RR-8434, INRIA. 2013. ⟨hal-00921157v2⟩



Record views


Files downloads