Flip Distance Between Triangulations of a Planar Point Set is APX-Hard

Alexander Pilz

Research output: Contribution to journalArticlepeer-review


In this work we consider triangulations of point sets in the Euclidean plane, i.e., maximal straight-line crossing-free graphs on a finite set of points. Given a triangulation of a point set, an edge flip is the operation of removing one edge and adding another one, such that the resulting graph is again a triangulation. Flips are a major way of locally transforming triangular meshes. We show that, given a point set S in the Euclidean plane and two triangulations T1 and T2 of S, it is an APX-hard problem to minimize the number of edge flips to transform T1 to T2 .
Original languageEnglish
Pages (from-to)589-604
JournalComputational Geometry
Publication statusPublished - 2014

Fields of Expertise

  • Information, Communication & Computing

Treatment code (Nähere Zuordnung)

  • Basic - Fundamental (Grundlagenforschung)


Dive into the research topics of 'Flip Distance Between Triangulations of a Planar Point Set is APX-Hard'. Together they form a unique fingerprint.

Cite this