Document Open Access Logo

Flipping Geometric Triangulations on Hyperbolic Surfaces

Authors Vincent Despré, Jean-Marc Schlenker, Monique Teillaud

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.35.pdf
  • Filesize: 0.75 MB
  • 16 pages

Document Identifiers

Author Details

Vincent Despré
  • Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France
Jean-Marc Schlenker
  • Department of Mathematics, University of Luxembourg, Luxembourg
Monique Teillaud
  • Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France

Funding

The authors were partially supported by the grant(s) ANR-17-CE40-0033 of the French National Research Agency ANR (project SoS) and INTER/ANR/16/11554412/SoS of the Luxembourg National Research fund FNR (https://members.loria.fr/Monique.Teillaud/collab/SoS/).

Cite AsGet BibTex

Vincent Despré, Jean-Marc Schlenker, and Monique Teillaud. Flipping Geometric Triangulations on Hyperbolic Surfaces. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.35

Abstract

We consider geometric triangulations of surfaces, i.e., triangulations whose edges can be realized by disjoint geodesic segments. We prove that the flip graph of geometric triangulations with fixed vertices of a flat torus or a closed hyperbolic surface is connected. We give upper bounds on the number of edge flips that are necessary to transform any geometric triangulation on such a surface into a Delaunay triangulation.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Discrete mathematics
  • Mathematics of computing → Geometric topology
Keywords
  • Hyperbolic surface
  • Topology
  • Delaunay triangulation
  • Algorithm
  • Flip graph

Metrics

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

References

  1. Marcel Berger. Geometry. Springer, 1996. Google Scholar
  2. Joan S Birman and Caroline Series. Geodesics with bounded intersection number on surfaces are sparsely distributed. Topology, 24(2):217-225, 1985. 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, Iordan Iordanov, and Monique Teillaud. 2D hyperbolic Delaunay triangulations. In CGAL User and Reference Manual. CGAL Editorial Board, 4.14 edition, 2019. URL: https://doc.cgal.org/latest/Manual/packages.html#PkgHyperbolicTriangulation2.
  5. 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:17, 2016. URL: https://doi.org/10.4230/LIPIcs.SoCG.2016.20.
  6. Manuel Caroli and Monique Teillaud. Delaunay triangulations of closed Euclidean d-orbifolds. Discrete & Computational Geometry, 55(4):827-853, 2016. URL: https://doi.org/10.1007/s00454-016-9782-6.
  7. Andrew J. Casson and Steven A. Bleiler. Automorphisms of surfaces after Nielsen and Thurston, volume 9 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 1988. URL: https://doi.org/10.1017/CBO9780511623912.
  8. Carmen Cortés, Clara I Grima, Ferran Hurtado, Alberto Márquez, Francisco Santos, and Jesus Valenzuela. Transforming triangulations on nonplanar surfaces. SIAM Journal on Discrete Mathematics, 24(3):821-840, 2010. URL: https://doi.org/10.1137/070697987.
  9. H. Edelsbrunner and R. Seidel. Voronoi diagrams and arrangements. Discrete & Computational Geometry, 1(1):25-44, 1986. URL: https://doi.org/10.1007/BF02187681.
  10. 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.
  11. Albert Fathi, François Laudenbach, and Valentin Poénaru. Thurston’s Work on Surfaces (MN-48). Princeton University Press, 2012. Google Scholar
  12. Albert Fathi, François Laudenbach, Valentin Poénaru, et al. Travaux de Thurston sur les surfaces, volume 66-67 of Astérisque. Société Mathématique de France, Paris, 1979. Google Scholar
  13. Martin Gardner. Chapter 19: Non-Euclidean geometry. In The Last Recreations. Springer, 1997. Google Scholar
  14. F. Hurtado, M. Noy, and J. Urrutia. Flipping edges in triangulations. Discrete & Computational Geometry, 3(22):333-346, 1999. URL: https://doi.org/10.1007/PL00009464.
  15. 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. URL: https://doi.org/10.4230/LIPIcs.SoCG.2017.44.
  16. Gregorii A Margulis. Applications of ergodic theory to the investigation of manifolds of negative curvature. Functional analysis and its applications, 3(4):335-336, 1969. Google Scholar
  17. William S. Massey. A basic course in algebraic topology, volume 127 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1991. Google Scholar
  18. Maryam Mirzakhani. Growth of the number of simple closed geodesics on hyperbolic surfaces. Annals of Mathematics, 168(1):97-125, 2008. Google Scholar
  19. Guillaume Tahar. Geometric triangulations and flips. C. R. Acad. Sci. Paris, Ser. I, 357:620–623, 2019. Google Scholar
  20. J. Trainin. An elementary proof of Pick’s theorem. Mathematical Gazette, 91(522):536-540, 2007. 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