JUCS - Journal of Universal Computer Science 2(8): 570-579, doi: 10.3217/jucs-002-08-0570
The Edge-Flipping Distance of Triangulations
expand article infoSabine Hanke‡, Thomas Ottmann§, Sven Schuierer‡
‡ Institut für Informatik, Universität Freiburg, Germany§ University of Freiburg, Germany

Corresponding author: Sabine Hanke ( hanke@informatik.uni-freiburg.de )

© Sabine Hanke, Thomas Ottmann, Sven Schuierer.
This article is freely available under the J.UCS Open Content License.
Citation: Hanke S, Ottmann T, Schuierer S (1996) The Edge-Flipping Distance of Triangulations. JUCS - Journal of Universal Computer Science 2(8): 570-579. https://doi.org/10.3217/jucs-002-08-0570
Open Access
Abstract
An edge-flipping operation in a triangulation T of a set of points in the plane is a local restructuring that changes T into a triangulation that differs from T in exactly one edge. The edge-flipping distance between two triangulations of the same set of points is the minimum number of edge-flipping operations needed to convert one into the other. In the context of computing the rotation distance of binary trees Sleator, Tarjan, and Thurston show an upper bound of 2n - 10 on the maximum edge-flipping distance between triangulations of convex polygons with n nodes, n > 12. Using volumetric arguments in hyperbolic 3-space they prove that the bound is tight. In this paper we establish an upper bound on the edge-flipping distance between triangulations of a general finite set of points in the plane by showing that no more edge-flipping operations than the number of intersections between the edges of two triangulations are needed to transform these triangulations into another, and we present an algorithm that computes such a sequence of edge-flipping operations.
Keywords
triangulation, edge-flipping operation, flip, edge-flipping distance, rotation distance