2026-07-22T21:03:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17877 2024-03-06T11:00:35Z ddc:004 open_access

Computing a Dirichlet Domain for a Hyperbolic Surface Despré, Vincent Kolbe, Benedikt Parlier, Hugo Teillaud, Monique Hyperbolic geometry Topology Voronoi diagram Algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vincent Despré and Benedikt Kolbe and Hugo Parlier and Monique Teillaud 2023 Is Part Of LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2023.27 urn:nbn:de:0030-drops-178771 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.27 eng https://creativecommons.org/licenses/by/4.0/legalcode