Minimal delaunay triangulations of hyperbolic surfaces

Matthijs Ebbens*, Hugo Parlier, Gert Vegter

*Corresponding author for this work

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

18 Downloads (Pure)

Abstract

Motivated by recent work on Delaunay triangulations of hyperbolic surfaces, we consider the minimal number of vertices of such triangulations. First, we show that every hyperbolic surface of genus g has a simplicial Delaunay triangulation with O(g) vertices, where edges are given by distance paths. Then, we construct a class of hyperbolic surfaces for which the order of this bound is optimal. Finally, to give a general lower bound, we show that the Ω(√g) lower bound for the number of vertices of a simplicial triangulation of a topological surface of genus g is tight for hyperbolic surfaces as well.

Original languageEnglish
Title of host publication37th International Symposium on Computational Geometry, SoCG 2021
EditorsKevin Buchin, Eric Colin de Verdiere
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages16
ISBN (Electronic)9783959771849
DOIs
Publication statusPublished - 1-Jun-2021
Event37th International Symposium on Computational Geometry, SoCG 2021 - Virtual, Buffalo, United States
Duration: 7-Jun-202111-Jun-2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume189
ISSN (Print)1868-8969

Conference

Conference37th International Symposium on Computational Geometry, SoCG 2021
Country/TerritoryUnited States
CityVirtual, Buffalo
Period07/06/202111/06/2021

Keywords

  • Delaunay triangulations
  • Hyperbolic surfaces
  • Metric graph embeddings
  • Moduli spaces

Cite this