The Flip Diameter of Rectangulations and Convex Subdivisions
Eyal Ackerman, Michelle M. Allen, Gill Barequet, Maarten Löffler, Joshua Mermelstein, Diane L. Souvaine, Csaba D. Tóth
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. Comment: 17 pages, 12 figures, an extended abstract has been presented at LATIN 2014
Keywords
Computer Science - Discrete Mathematics
Computer Science - Computational Geometry
Mathematics - Combinatorics
Cited by
Source: OpenCitations
Reconfiguration of Plane Trees in Convex Geometric Graphs
Discrete & Computational Geometry
Authors : Nicolas Bousquet, Lucas De Meyer, Théo Pierron, Alexandra Wesolek
