LIPIcs.SoCG.2017.44.pdf
- Filesize: 1.21 MB
- 15 pages
Document
Implementing Delaunay Triangulations of the Bolza Surface
Authors
-
Part of:
Volume:
33rd International Symposium on Computational Geometry (SoCG 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-06-20
Cite As Get BibTex
Iordan Iordanov and Monique Teillaud. Implementing Delaunay Triangulations of the Bolza Surface. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SoCG.2017.44
Abstract
The CGAL library offers software packages to compute Delaunay triangulations of the (flat) torus of genus one in two and three dimensions. To the best of our knowledge, there is no available software for the simplest possible extension, i.e., the Bolza surface, a hyperbolic manifold homeomorphic to a torus of genus two. In this paper, we present an implementation based on the theoretical results and the incremental algorithm proposed last year at SoCG by Bogdanov, Teillaud, and Vegter. We describe the representation of the triangulation, we detail the different steps of the algorithm, we study predicates, and report experimental results.
Subject Classification
Keywords
- hyperbolic surface
- Fuchsian group
- arithmetic issues
- Dehn's algorithm
- CGAL
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- N. L. Balazs and A. Voros. Chaos on the pseudosphere. Physics Reports, 143(3):109-240, 1986. URL: http://dx.doi.org/10.1016/0370-1573(86)90159-6.
- Mikhail Bogdanov, Monique Teillaud, and Gert Vegter. Delaunay triangulations on orientable surfaces of low genus. In Proceedings of the Thirty-second International Symposium on Computational Geometry, pages 20:1-20:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.20.
- A. Bowyer. Computing Dirichlet tessellations. The Computer Journal, 24(2):162-166, 1981. URL: http://dx.doi.org/10.1093/comjnl/24.2.162.
- Manuel Caroli and Monique Teillaud. 3D periodic triangulations. In CGAL User and Reference Manual. CGAL Editorial Board, 3.5 (and further) edition, 2009-. URL: http://doc.cgal.org/latest/Manual/packages.html#PkgPeriodic3Triangulation3Summary.
- Manuel Caroli and Monique Teillaud. Delaunay triangulations of closed Euclidean d-orbifolds. Discrete &Computational Geometry, 55(4):827-853, 2016. URL: http://dx.doi.org/10.1007/s00454-016-9782-6.
- M. Dehn. Transformation der Kurven auf zweiseitigen Flächen. Mathematische Annalen, 72(3):413-421, 1912. URL: http://dx.doi.org/10.1007/BF01456725.
- Olivier Devillers, Sylvain Pion, and Monique Teillaud. Walking in a triangulation. International Journal of Foundations of Computer Science, 13:181-199, 2002. URL: https://hal.inria.fr/inria-00102194.
- Olivier Devillers and Monique Teillaud. Perturbations for Delaunay and weighted Delaunay 3D Triangulations. Computational Geometry: Theory and Applications, 44:160-168, 2011. URL: http://dx.doi.org/10.1016/j.comgeo.2010.09.010.
-
Nikolai P. Dolbilin and Daniel H. Huson. Periodic Delone tilings. Periodica Mathematica Hungarica, 34:1-2:57-64, 1997.
- The GAP Group. GAP - Groups, Algorithms, and Programming, Version 4.8.6, 2016. URL: http://www.gap-system.org.
- Martin Greendlinger. Dehn’s algorithm for the word problem. Communications on Pure and Applied Mathematics, 13(1):67-83, 1960. URL: http://dx.doi.org/10.1002/cpa.3160130108.
- Nico Kruithof. 2D periodic triangulations. In CGAL User and Reference Manual. CGAL Editorial Board, 4.3 (and further) edition, 2013-. URL: http://doc.cgal.org/latest/Manual/packages.html#PkgPeriodic2Triangulation2Summary.
- The Magma Development Team. Magma Computational Algebra System. URL: http://magma.maths.usyd.edu.au/magma/.
- John Joseph O'Connor and Edmund Frederick Robertson. The MacTutor History of Mathematics archive, 2003. URL: http://www-history.mcs.st-andrews.ac.uk/HistTopics/Word_problems.html.
- C. K. Yap and T. Dubé. The exact computation paradigm. In D.-Z. Du and F. K. Hwang, editors, Computing in Euclidean Geometry, volume 4 of Lecture Notes Series on Computing, pages 452-492. World Scientific, Singapore, 2nd edition, 1995. URL: http://dx.doi.org/10.1142/9789812831699_0011.
- Chee Yap et al. The CORE Library Project. URL: http://cs.nyu.edu/exact/core_pages/intro.html.