Flips in edge-labelled pseudo-triangulations (Q680154)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Flips in edge-labelled pseudo-triangulations |
scientific article |
Statements
Flips in edge-labelled pseudo-triangulations (English)
0 references
22 January 2018
0 references
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.
0 references
edge flip
0 references
diagonal flip
0 references
pseudo-triangulation
0 references
edge-label
0 references