The Flip Diameter of Rectangulations and Convex Subdivisions
Authors: Ackerman, Eyal and Allen, Michelle M. and Barequet, Gill and Löffler, Maarten and Mermelstein, Joshua and Souvaine, Diane L. and Tóth, Csaba D.
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.