Delaunay triangulations and cycles on closed hyperbolic surfaces - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2013

Delaunay triangulations and cycles on closed hyperbolic surfaces

(1) , (1)
1
Mikhail Bogdanov
  • Function : Author
  • PersonId : 933126
Monique Teillaud

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.
Ce travail est motivé par les applications des triangulations de Delaunay périodiques dans le modèle du disque de Poincaré, modèle conforme du plan hyperbolique H^2. Une triangulation périodique est définie par un ensemble infini de points, image d'un ensemble fini par un groupe discret (non commutatif) G engendré par des translations, et tel que l'aire hyperbolique d'un domaine de Dirichlet soit finie (c'est-à-dire un groups fuchsien cocompact agissant sur H^2 sans point fixe). Nous considérons la projection d'une telle triangulation de Delaunay sur la surface hyperbolique fermée orientable M = H^2/G. Le graphe des arêtes de cette projection peut avoir des cycles de longueur un ou deux. Nous démontrons qu'il existe toujours un revêtement fini de M dans lequel il n'y a pas de cycle de longueur <= 2. Nous nous concentrons ensuite sur le groupe définissant la surface de Bolza (homéomorphe à un tore à deux anses), et nous construisons explicitement une suite de sous-groupes d'indice fini nous permettant d'exhiber un revêtement de la surface de Bolza dans lequel, quel que soit l'ensemble de points, il n'y a aucun cycle de longueur un, et un autre revêtement dans lequel il n'y a aucun cycle de longueur deux. Nous présentons aussi un petit ensemble de points tel que la projection de la triangulation de Delaunay de tout sur-ensemble sur la surface de Bolza n'a aucun cycle de longueur <= 2. Ce travail utilise des démonstrations mathématiques, des constructions algorithmiques, et de la programmation.
Fichier principal
Vignette du fichier
RR-8434-revised.pdf (1.07 Mo) Télécharger le fichier
Vignette du fichier
V1.png (2.17 Mo) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Figure, Image
Loading...

Dates and versions

hal-00921157 , version 1 (19-12-2013)
hal-00921157 , version 2 (13-04-2014)

Identifiers

  • HAL Id : hal-00921157 , version 2

Cite

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

Share

Gmail Facebook Twitter LinkedIn More