2004-12-01
Reconfiguring triangulations with edge flips and point moves
Publication
Publication
Presented at the
12th International Symposium on Graph Drawing, GD 2004 (September 2004)
We examine reconfigurations between triangulations and near-triangulations of point sets, and give new bounds on the number of point moves and edge flips sufficient for any reconfiguration. We show that with O(n log n) edge flips and point moves, we can transform any geometric near-triangulation on n points to any other geometric near-triangulation on n possibly different points. This improves the previously known bound of O(n 2) edge flips and point moves.
Additional Metadata | |
---|---|
12th International Symposium on Graph Drawing, GD 2004 | |
Organisation | School of Computer Science |
Aloupis, G, Bose, P, & Morin, P. (2004). Reconfiguring triangulations with edge flips and point moves. Presented at the 12th International Symposium on Graph Drawing, GD 2004.
|