TY - GEN
T1 - Minimal delaunay triangulations of hyperbolic surfaces
AU - Ebbens, Matthijs
AU - Parlier, Hugo
AU - Vegter, Gert
N1 - Funding Information:
Funding Hugo Parlier: Research partially supported by ANR/FNR project SoS, INTER/ANR/16/11554412/SoS, ANR-17-CE40-0033.
Publisher Copyright:
© Matthijs Ebbens, Hugo Parlier, and Gert Vegter; licensed under Creative Commons License CC-BY 4.0 37th International Symposium on Computational Geometry (SoCG 2021).
PY - 2021/6/1
Y1 - 2021/6/1
N2 - 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.
AB - 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.
KW - Delaunay triangulations
KW - Hyperbolic surfaces
KW - Metric graph embeddings
KW - Moduli spaces
UR - http://www.scopus.com/inward/record.url?scp=85108233980&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SoCG.2021.31
DO - 10.4230/LIPIcs.SoCG.2021.31
M3 - Conference contribution
AN - SCOPUS:85108233980
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 37th International Symposium on Computational Geometry, SoCG 2021
A2 - Buchin, Kevin
A2 - de Verdiere, Eric Colin
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 37th International Symposium on Computational Geometry, SoCG 2021
Y2 - 7 June 2021 through 11 June 2021
ER -