Document Open Access Logo

Minimal Delaunay Triangulations of Hyperbolic Surfaces

Authors Matthijs Ebbens, Hugo Parlier, Gert Vegter

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.31.pdf
  • Filesize: 0.89 MB
  • 16 pages

Document Identifiers

Author Details

Matthijs Ebbens
  • Bernoulli Institute for Mathematics, Computer Science and Artificial Intelligence, University of Groningen, The Netherlands
Hugo Parlier
  • Mathematics Research Unit, University of Luxembourg, Luxembourg
Gert Vegter
  • Bernoulli Institute for Mathematics, Computer Science and Artificial Intelligence, University of Groningen, The Netherlands

Funding

  • Parlier, Hugo: Research partially supported by ANR/FNR project SoS, INTER/ANR/16/11554412/SoS, ANR-17-CE40-0033.

Acknowledgements

The authors warmly thank Monique Teillaud and Vincent Despré for fruitful discussions. We would also like to thank the referees for their helpful comments.

Cite AsGet BibTex

Matthijs Ebbens, Hugo Parlier, and Gert Vegter. Minimal Delaunay Triangulations of Hyperbolic Surfaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.31

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Geometric topology
  • Mathematics of computing → Graphs and surfaces
Keywords
  • Delaunay triangulations
  • hyperbolic surfaces
  • metric graph embeddings
  • moduli spaces

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Alan F. Beardon. The geometry of discrete groups, volume 91 of Graduate Texts in Mathematics. Springer-Verlag, 2012. Google Scholar
  2. Lipman Bers. An inequality for Riemann surfaces. In Differential geometry and complex analysis, pages 87-93. Springer, Berlin, 1985. Google Scholar
  3. Mikhail Bogdanov and Monique Teillaud. Delaunay triangulations and cycles on closed hyperbolic surfaces. Technical Report RR-8434, INRIA, 2013. Google Scholar
  4. Mikhail Bogdanov, Monique Teillaud, and Gert Vegter. Delaunay triangulations on orientable surfaces of low genus. In Leibniz International Proceedings in Informatics, editor, 32nd International Symposium on Computational Geometry (SoCG 2016), pages 20:1-20:17, 2016. Google Scholar
  5. Adrian Bowyer. Computing Dirichlet tessellations. The Computer Journal, 24(2):162-166, 1981. Google Scholar
  6. Peter Buser. Geometry and spectra of compact Riemann surfaces. Springer-Verlag, 2010. Google Scholar
  7. Vincent Despré, Jean-Marc Schlenker, and Monique Teillaud. Flipping geometric triangulations on hyperbolic surfaces. arXiv preprint, 2019. URL: http://arxiv.org/abs/1912.04640.
  8. István Fáry. On straight-line representation of planar graphs. Acta scientiarum mathematicarum, 11(229-233):2, 1948. Google Scholar
  9. Larry Guth, Hugo Parlier, and Robert Young. Pants decompositions of random surfaces. Geom. Funct. Anal., 21(5):1069-1090, 2011. Google Scholar
  10. Alfredo Hubard, Vojtěch Kaluža, Arnaud De Mesmay, and Martin Tancer. Shortest path embeddings of graphs on surfaces. Discrete & Computational Geometry, 58(4):921-945, 2017. Google Scholar
  11. Iordan Iordanov and Monique Teillaud. Implementing Delaunay triangulations of the Bolza surface. In Proceedings of the Thirty-third International Symposium on Computational Geometry, pages 44:1-44:15, 2017. Google Scholar
  12. Mark Jungerman and Gerhard Ringel. Minimal triangulations on orientable surfaces. Acta Mathematica, 145(1):121-154, 1980. Google Scholar
  13. Maryam Mirzakhani. Growth of Weil-Petersson volumes and random hyperbolic surfaces of large genus. J. Differential Geom., 94(2):267-300, 2013. Google Scholar
  14. Hugo Parlier and Camille Petit. Chromatic numbers of hyperbolic surfaces. Indiana University Mathematics Journal, pages 1401-1423, 2016. Google Scholar
  15. Gerhard Ringel and John W.T. Youngs. Solution of the Heawood map-coloring problem. Proceedings of the National Academy of Sciences, 60(2):438-445, 1968. Google Scholar
  16. John Stillwell. Geometry of surfaces. Springer-Verlag, 1992. Google Scholar
  17. Roberto Tamassia. Handbook of graph drawing and visualization. Chapman and Hall/CRC, 2013. Google Scholar
  18. Charles M. Terry, Lloyd R. Welch, and John W.T. Youngs. The genus of K_12s. Journal of Combinatorial Theory, 2(1):43-60, 1967. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact