Flips in edge-labelled pseudo-triangulations (Q680154)

The authors study particular pseudo-triangulations in the plane. A simple polygon with three convex interior angles that are connected by reflex chains is called a pseudo-triangle. Given a set \(P\) of \(n\) points in the plane, a pseudo-triangulation of \(P\) is a subdivision of its convex hull into pseudo-triangles. It is a pointed pseudo-triangulation if all vertices are incident to a reflex angle in some face. Moreover, a triangulation is edge-labelled if each edge has a unique label. Different kinds of edge flips can be used to transform one pseudo-triangulation into another such triangulation. The authors show that \(O(n^2)\) exchanging flips suffice to transform any edge-labelled pointed pseudo-triangulation into any other with the same set of labels. Moreover, using insertion, deletion and exchanging flips, they show that any edge-labelled pseudo-triangulation can be transformed 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.