[en] 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.
Disciplines :
Mathematics
Author, co-author :
Despré, Vincent ✱; Université de Lorraine, CNRS, Inria, LORIA, Nancy, France
Kolbe, Benedikt ✱; Hausdorff Center for Mathematics, Universität Bonn, Germany
PARLIER, Hugo ✱; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Mathematics (DMATH)
Teillaud, Monique ✱; Université de Lorraine, CNRS, Inria, LORIA, Nancy, France
✱ These authors have contributed equally to this work.
External co-authors :
yes
Language :
English
Title :
Computing a Dirichlet Domain for a Hyperbolic Surface
Publication date :
June 2023
Event name :
SoCG
Event place :
Dallas, Usa
Event date :
12-06-2023 => 15-06-2023
Main work title :
39th International Symposium on Computational Geometry, SoCG 2023
Editor :
Chambers, Erin W.
Publisher :
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN/EAN :
978-3-9597727-3-0
Peer reviewed :
Peer reviewed
Funding text :
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/. Benedikt Kolbe: 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.
N.L. Balazs and A. Voros. Chaos on the pseudosphere. Physics Reports, 143(3):109-240, 1986. doi:10.1016/0370-1573(86)90159-6.
Alan F. Beardon. The Geometry of Discrete Groups. Springer-Verlag, 1983.
Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud. Hyperbolic Delaunay complexes and Voronoi diagrams made practical. Journal of Computational Geometry, 5:56-85, 2014. doi:10.20382/jocg.v5i1a4.
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. doi:10.4230/LIPIcs.SoCG.2016.20.
Peter Buser. Geometry and spectra of compact Riemann surfaces. Modern Birkhäuser classics. Birkhäuser, Boston, Mass., 2nd edition, 2010.
H. S. M. Coxeter and W. O. J. Moser. Generators and Relations for Discrete Groups. Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1957.
Jason DeBlois. The centered dual and the maximal injectivity radius of hyperbolic surfaces. Geometry and Topology, 19(2):953-1014, 2015. doi:10.2140/gt.2015.19.953.
Jason DeBlois. The Delaunay tessellation in hyperbolic space. Mathematical Proceedings of the Cambridge Philosophical Society, 164(1):15-46, 2018. doi:10.1017/S0305004116000827.
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/.
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.
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. doi:10.4230/LIPIcs.SoCG.2020.35.
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. doi:10.4230/LIPIcs.SoCG.2021.31.
David Eppstein. Dynamic generators of topologically embedded graphs. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 599-608, 2003.
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.
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. doi:10.4230/LIPIcs.SoCG.2017.44.
Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins University Press, Baltimore, 2001.
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. doi:10.1038/s41586-021-04328-y.
James Rickards. Improved computation of fundamental domains for arithmetic Fuchsian groups. Mathematics of Computation, 91:2929-2954, 2022. doi:10.1090/mcom/3777.
John Voight. Computing fundamental domains for Fuchsian groups. Journal de Théorie des Nombres de Bordeaux, 21(2):467-489, 2009. doi:10.5802/jtnb.683.
