License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.35
URN: urn:nbn:de:0030-drops-121939
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12193/
Go to the corresponding LIPIcs Volume Portal

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

Flipping Geometric Triangulations on Hyperbolic Surfaces

pdf-format:
LIPIcs-SoCG-2020-35.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{despr_et_al:LIPIcs:2020:12193,
  author =	{Vincent Despr{\'e} and Jean-Marc Schlenker and Monique Teillaud},
  title =	{{Flipping Geometric Triangulations on Hyperbolic Surfaces}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12193},
  URN =		{urn:nbn:de:0030-drops-121939},
  doi =		{10.4230/LIPIcs.SoCG.2020.35},
  annote =	{Keywords: Hyperbolic surface, Topology, Delaunay triangulation, Algorithm, Flip graph}
}

Keywords: Hyperbolic surface, Topology, Delaunay triangulation, Algorithm, Flip graph
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI