Ackerman, Eyal and Allen, Michelle M. and Barequet, Gill and Löffler, Maarten and Mermelstein, Joshuaet al. - The Flip Diameter of Rectangulations and Convex Subdivisions

dmtcs:1413 - Discrete Mathematics & Theoretical Computer Science, March 17, 2016, Vol. 18 no. 3
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.


Source : oai:arXiv.org:1312.4429
Volume: Vol. 18 no. 3
Section: Combinatorics
Published on: March 17, 2016
Submitted on: March 16, 2016
Keywords: Computer Science - Discrete Mathematics,Computer Science - Computational Geometry,Mathematics - Combinatorics


Share

Browsing statistics

This page has been seen 276 times.
This article's PDF has been downloaded 170 times.