[en] We consider geometric triangulations of surfaces, i.e., triangulations whose edges can be realized by disjoint locally 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.
Disciplines :
Sciences informatiques
Auteur, co-auteur :
Despré, vincent
SCHLENKER, Jean-Marc ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC)
Teillaud, Monique
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
Flipping Geometric Triangulations on Hyperbolic Surfaces
Joan S Birman and Caroline Series. Geodesics with bounded intersection number on surfaces are sparsely distributed. Topology, 24(2):217-225, 1985.
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, 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.
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. doi:10.4230/LIPIcs.SoCG.2016.20.
Manuel Caroli and Monique Teillaud. Delaunay triangulations of closed Euclidean d-orbifolds. Discrete & Computational Geometry, 55(4):827-853, 2016. URL: http://hal.inria.fr/ hal-01294409, doi:10.1007/s00454-016-9782-6.
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. doi:10.1017/CBO9780511623912.
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. doi:10.1137/070697987.
H. Edelsbrunner and R. Seidel. Voronoi diagrams and arrangements. Discrete & Computational Geometry, 1(1):25-44, 1986. doi:10.1007/BF02187681.
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.
Albert Fathi, François Laudenbach, and Valentin Poénaru. Thurston's Work on Surfaces (MN-48). Princeton University Press, 2012.
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.
Martin Gardner. Chapter 19: Non-Euclidean geometry. In The Last Recreations. Springer, 1997.
F. Hurtado, M. Noy, and J. Urrutia. Flipping edges in triangulations. Discrete & Computational Geometry, 3(22):333-346, 1999. doi:10.1007/PL00009464.
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. doi:10.4230/LIPIcs.SoCG.2017.44.
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.
William S. Massey. A basic course in algebraic topology, volume 127 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1991.
Maryam Mirzakhani. Growth of the number of simple closed geodesics on hyperbolic surfaces. Annals of Mathematics, 168(1):97-125, 2008.
Guillaume Tahar. Geometric triangulations and flips. C. R. Acad. Sci. Paris, Ser. I, 357:620-623, 2019.
J. Trainin. An elementary proof of Pick's theorem. Mathematical Gazette, 91(522):536-540, 2007.
