Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949142 | Computational Geometry | 2017 | 10 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Prosenjit Bose, Sander Verdonschot,