Flipping Geometric Triangulations on Hyperbolic Surfaces

Despré, vincent; Schlenker, Jean-Marc; Teillaud, Monique

Download

Paper published in a book (Scientific congresses, symposiums and conference proceedings)

Flipping Geometric Triangulations on Hyperbolic Surfaces

Despré, vincent; Schlenker, Jean-Marc; Teillaud, Monique

2020 • In symposium on computational geometry (SoCG)

Peer reviewed

Permalink
https://hdl.handle.net/10993/41363

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

1912.04640.pdf

Publisher postprint (698.75 kB)

Download

All documents in ORBilu are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Abstract :

[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 :

Computer science

Author, co-author :

Despré, vincent

Schlenker, Jean-Marc ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC)

Teillaud, Monique

External co-authors :

yes

Language :

English

Title :

Flipping Geometric Triangulations on Hyperbolic Surfaces

Publication date :

2020

Event name :

symposium on computational geometry (SoCG) 2020

Event date :

23-26-06-2020

Audience :

International

Main work title :

symposium on computational geometry (SoCG)

Pages :

35:1--35:16

Peer reviewed :

Peer reviewed

Focus Area :

Computational Sciences

Available on ORBilu :

since 20 December 2019

Statistics

Number of views

64 (0 by Unilu)

Number of downloads

30 (0 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

Bibliography

Marcel Berger. Geometry. Springer, 1996.
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.