2015-01-01
Flips in edge-labelled pseudo-triangulations
Publication
Publication
Presented at the
27th Canadian Conference on Computational Geometry, CCCG 2015 (August 2015), Kingston
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.
| Additional Metadata | |
|---|---|
| Conference | 27th Canadian Conference on Computational Geometry, CCCG 2015 |
| Citation |
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).
|