### Technical Report No. 76, February 1996 - Abstract

**Sabine Hanke, Thomas Ottmann and Sven Schuierer:**

*The edge-flipping distance of triangulations*

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 set of points in the plane by showing that not 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. Furthermore in the case
of triangulations of convex polygons we present a combinatorical proof
of a weaker lower bound of *3/2 n -5* with the aid of two
triangulations.

report76.ps.gz