The Flip Diameter of Rectangulations and Convex Subdivisions

We study the configuration space of rectanulations and convex subdivisions of n points in the plane. It is shown that a sequence of O(nlogn) elementary flip and rotate operations can transform any rectangulation to any other rectangulation on the same set of n points. This bound is the best possible for some point sets, while Θ(n) operations are sufficient and necessary for others. Some of our bounds generalize to convex subdivisions of n points in the plane.

keywords: Computational Geometry, Graphs Theory

Journal Article (peer-reviewed)

Csaba Tóth, Diane Souvaine, Eyal Ackerman, Gill Barequet, Joshua Mermelstein, Maarten Löffler, Michelle Allen
The Flip Diameter of Rectangulations and Convex Subdivisions
Discrete Mathematics & Theoretical Computer Science
18, 3, 2016
http://dmtcs.episciences.org/1413

Conference Proceedings (peer-reviewed)

Csaba Tóth, Diane Souvaine, Eyal Ackerman, Gill Barequet, Joshua Mermelstein, Maarten Löffler, Michelle Allen
The Flip Diameter of Rectangulations and Convex Subdivisions
Proc. 11th Latin American Symposium on Theoretical Informatics
LNCS 8392, 478–489, 2014
http://dx.doi.org/10.1007/978-3-642-54423-1_42

Archived Publication (not reviewed)

Csaba Tóth, Diane Souvaine, Eyal Ackerman, Gill Barequet, Joshua Mermelstein, Maarten Löffler, Michelle Allen
The Flip Diameter of Rectangulations and Convex Subdivisions
1312.4429, 2013
http://arXiv.org/abs/1312.4429

back to list