Transforming pseudo-triangulations
We study the problem of transforming pseudo-triangulations in the plane. We show that a pseudo-triangulation with n vertices can be transformed into another one using O(n log n) flips only. This improves the previous bound O(n(2)) of Bronnimann et al. [Fall Workshop on Comput. Geometry, 2001]. We present an algorithm for computing a transformation between two pseudo-triangulations in O((f + n) log n) time where f is the number of flips. (C) 2004 Elsevier B.V. All rights reserved.
pseudo-triangulations flips pseudo-triangles analysis of algorithms computational geometry triangulation of a polygon