Document Open Access Logo

Computing a Dirichlet Domain for a Hyperbolic Surface

Authors Vincent Despré, Benedikt Kolbe, Hugo Parlier, Monique Teillaud

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2023.27.pdf
  • Filesize: 1.21 MB
  • 15 pages

Document Identifiers

Author Details

Vincent Despré
  • Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
Benedikt Kolbe
  • Hausdorff Center for Mathematics, Universität Bonn, Germany
Hugo Parlier
  • Department of Mathematics, University of Luxembourg, Luxembourg
Monique Teillaud
  • Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

Funding

This work was partially supported by grant ANR-17-CE40-0033 of the French National Research Agency ANR and INTER/ANR/16/11554412/SoS of the Luxembourg National Research fund FNR. Website of the SoS project: https://SoS.loria.fr/.
  • Kolbe, Benedikt: This work was done while this author was working at Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

Acknowledgements

The authors wish to thank the anonymous reviewer who suggested this simpler version of Section 4.

Cite As Get BibTex

Vincent Despré, Benedikt Kolbe, Hugo Parlier, and Monique Teillaud. Computing a Dirichlet Domain for a Hyperbolic Surface. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SoCG.2023.27

Abstract

This paper exhibits and analyzes an algorithm that takes a given closed orientable hyperbolic surface and outputs an explicit Dirichlet domain. The input is a fundamental polygon with side pairings. While grounded in topological considerations, the algorithm makes key use of the geometry of the surface. We introduce data structures that reflect this interplay between geometry and topology and show that the algorithm runs in polynomial time, in terms of the initial perimeter and the genus of the surface.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Geometric topology
  • Theory of computation → Computational geometry
Keywords
  • Hyperbolic geometry
  • Topology
  • Voronoi diagram
  • Algorithm

Metrics

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

References

  1. N.L. Balazs and A. Voros. Chaos on the pseudosphere. Physics Reports, 143(3):109-240, 1986. URL: https://doi.org/10.1016/0370-1573(86)90159-6.
  2. Alan F. Beardon. The Geometry of Discrete Groups. Springer-Verlag, 1983. Google Scholar
  3. Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud. Hyperbolic Delaunay complexes and Voronoi diagrams made practical. Journal of Computational Geometry, 5:56-85, 2014. URL: https://doi.org/10.20382/jocg.v5i1a4.
  4. Mikhail Bogdanov, Monique Teillaud, and Gert Vegter. Delaunay triangulations on orientable surfaces of low genus. In Sándor Fekete and Anna Lubiw, editors, 32nd International Symposium on Computational Geometry (SoCG 2016), volume 51 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1-20:17, Dagstuhl, Germany, 2016. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2016.20.
  5. Peter Buser. Geometry and spectra of compact Riemann surfaces. Modern Birkhäuser classics. Birkhäuser, Boston, Mass., 2nd edition, 2010. Google Scholar
  6. H. S. M. Coxeter and W. O. J. Moser. Generators and Relations for Discrete Groups. Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1957. Google Scholar
  7. Jason DeBlois. The centered dual and the maximal injectivity radius of hyperbolic surfaces. Geometry and Topology, 19(2):953-1014, 2015. URL: https://doi.org/10.2140/gt.2015.19.953.
  8. Jason DeBlois. The Delaunay tessellation in hyperbolic space. Mathematical Proceedings of the Cambridge Philosophical Society, 164(1):15-46, 2018. URL: https://doi.org/10.1017/S0305004116000827.
  9. Vincent Despré, Loïc Dubois, Benedikt Kolbe, and Monique Teillaud. Experimental analysis of Delaunay flip algorithms on genus two hyperbolic surfaces. Preprint, INRIA, May 2021. URL: https://hal.inria.fr/hal-03462834/.
  10. Vincent Despré, Benedikt Kolbe, and Monique Teillaud. Representing infinite hyperbolic periodic Delaunay triangulations using finitely many Dirichlet domains. Preprint, INRIA, July 2021. URL: https://hal.inria.fr/hal-03045921.
  11. Vincent Despré, Jean-Marc Schlenker, and Monique Teillaud. Flipping geometric triangulations on hyperbolic surfaces. In Sergio Cabello and Danny Z. Chen, editors, 36th International Symposium on Computational Geometry (SoCG 2020), volume 164 of Leibniz International Proceedings in Informatics (LIPIcs), pages 35:1-35:16, Dagstuhl, Germany, 2020. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2020.35.
  12. Matthijs Ebbens, Hugo Parlier, and Gert Vegter. Minimal Delaunay triangulations of hyperbolic surfaces. In Kevin Buchin and Éric Colin de Verdière, editors, 37th International Symposium on Computational Geometry (SoCG 2021), volume 189 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-31:16, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.31.
  13. David Eppstein. Dynamic generators of topologically embedded graphs. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 599-608, 2003. Google Scholar
  14. Benson Farb and Dan Margalit. A Primer on Mapping Class Groups (PMS-49). Princeton University Press, 2012. URL: http://www.jstor.org/stable/j.ctt7rkjw.
  15. Iordan Iordanov and Monique Teillaud. Implementing Delaunay triangulations of the Bolza surface. In Boris Aronov and Matthew J. Katz, editors, 33rd International Symposium on Computational Geometry (SoCG 2017), volume 77 of Leibniz International Proceedings in Informatics (LIPIcs), pages 44:1-44:15, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2017.44.
  16. Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins University Press, Baltimore, 2001. Google Scholar
  17. Nikolai C Passler, Xiang Ni, Guangwei Hu, Joseph R Matson, Giulia Carini, Martin Wolf, Mathias Schubert, Andrea Alù, Joshua D Caldwell, Thomas G Folland, et al. Hyperbolic shear polaritons in low-symmetry crystals. Nature, 602(7898):595-600, 2022. URL: https://doi.org/10.1038/s41586-021-04328-y.
  18. James Rickards. Improved computation of fundamental domains for arithmetic Fuchsian groups. Mathematics of Computation, 91:2929-2954, 2022. URL: https://doi.org/10.1090/mcom/3777.
  19. John Voight. Computing fundamental domains for Fuchsian groups. Journal de Théorie des Nombres de Bordeaux, 21(2):467-489, 2009. URL: https://doi.org/10.5802/jtnb.683.
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 About DROPS Imprint Privacy Contact