Adapting (Pseudo)-Triangulations with a Near-Linear Number of Edge
O. Aichholzer, F. Aurenhammer, and H. Krasser
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
, 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