Flipping edges in triangulations

In this paper we study the problem of flipping edges in triangulations of p olygons and point sets. One of the main results is that any triangulation o f a set of n points in general position contains at least inverted right pe rpendicular(n - 4)/2inverted left perpendicular edges that can be flipped. We also prove that O(n + k(2)) flips are sufficient to transform any triang ulation of an n-gon with k reflex vertices into any other triangulation. We produce examples of n-gons with triangulations T and T' such that to trans form T into T' requires Ohm(n(2)) flips. Finally we show that if a set of n points has k convex layers, then any triangulation of the point set can be transformed into any other triangulation using at most O (kn) flips.