Flips in Edge-Labelled Pseudo-Triangulations

2015/12/04 by Prosenjit Bose, Bose, Prosenjit, Sander Verdonschot +1
Computer Science · Engineering · #Computational Geometry and Mesh Generation #graph theory and CDMA systems #Digital Image Processing Techniques

paper · pdf · doi:10.48550/arxiv.1512.01485

Abstract

We show that O(n²) 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.

Related

• Transformed flips in triangulations and matchings
• A Proof of the Orbit Conjecture for Flipping Edge-Labelled\n Triangulations
• Practical Reduction of Edge Flip Sequences in Two-Dimensional Triangulations
• Flip Graphs of Pseudo-Triangulations With Face Degree at Most 4
• Regular flip equivalence of surface triangulations