Reconfiguring Triangulations with Edge Flips and Point Moves

Aloupis, Greg and Bose, Prosenjit and Morin, Pat (2004) Reconfiguring Triangulations with Edge Flips and Point Moves. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004 , pp. 1-11(Official URL:

Full text not available from this repository.


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. Research supported in part by the Natural Science and Engineering Council of Canada.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-31843-9_1
Classifications: Z Theory > Z.250 Geometry

Actions (login required)

View Item View Item