Flips in edge-labelled pseudo-triangulations
We show that O(n2) exchanging flips suffice to transform any edge-labelled pointed pseudo-triangulation into any other with the same set of labels. By using insertion, deletion and exchanging flips, we can transform any edge-labelled pseudo-triangulation into any other with O(n log c + h log h) flips, where c is the number of convex layers and h is the number of points on the convex hull.
|Conference||27th Canadian Conference on Computational Geometry, CCCG 2015|
Bose, P, & Verdonschot, S. (Sander). (2015). Flips in edge-labelled pseudo-triangulations. In Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015 (pp. 63–69).