The Flip Diameter of Rectangulations and Convex Subdivisions

Abstract

We study the configuration space of rectangulations and convex subdivisions of $n$ points in the plane. It is shown that a sequence of $O(n\log n)$ 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 $\Theta (n)$ operations are sufficient and necessary for others. Some of our bounds generalize to convex subdivisions of $n$ points in the plane.

17 pages, 12 figures, an extended abstract has been presented at LATIN 2014

References in corpus (2)

• Bijections for Baxter Families and Related Objects
• Adjacency-Preserving Spatial Treemaps

Cited by in corpus (1)

• A Note on Flips in Diagonal Rectangulations