Given a set of n points in the plane, 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(nlog⁡c+hlog⁡h) flips, where c is the number of convex layers and h is the number of points on the convex hull.

Additional Metadata
Keywords Diagonal flip, Edge flip, Edge label, Pseudo-triangulation
Persistent URL dx.doi.org/10.1016/j.comgeo.2016.08.001
Journal Computational Geometry
Citation
Bose, P, & Verdonschot, S. (Sander). (2017). Flips in edge-labelled pseudo-triangulations. Computational Geometry, 60, 45–54. doi:10.1016/j.comgeo.2016.08.001