Adapting (Pseudo)-Triangulations with a Near-Linear Number of Edge Flips

O. Aichholzer, F. Aurenhammer, and H. Krasser

Abstract:

We provide two results on flip distances in pseudo-triangulations - for minimum pseudo-triangulations when using traditional flips operations, as well as for triangulations when a novel and natural edge flip operation is included into the repertoire of admissible flips. The obtained flip distance lengths are $O(n \log^2 n)$ and $O(n \log n)$, respectively. Our results partially rely on new partitioning results for pseudo-triangulations which may be of separate interest.

Reference: O. Aichholzer, F. Aurenhammer, and H. Krasser. Adapting (pseudo)-triangulations with a near-linear number of edge flips. In Lecture Notes in Computer Science 2748, Proc. 8th International Workshop on Algorithms and Data Structures (WADS), volume 2748, pages 12-24, 2003.