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). We present an algorithm for computing a transformation between two pseudo-triangulations in O((f + n) log n) time where / is the number of flips.