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 :
Reports
Complete list of metadatas

Cited literature [37 references]  Display  Hide  Download


https://hal.inria.fr/hal-00921157
Contributor : Monique Teillaud <>
Submitted on : Sunday, April 13, 2014 - 4:20:49 PM
Last modification on : Wednesday, October 30, 2019 - 7:36:17 PM
Long-term archiving on : Sunday, July 13, 2014 - 10:40:51 AM

Files

RR-8434-revised.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00921157, version 2

Collections

Citation

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

Share

Metrics

Record views

388

Files downloads

503