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

dmtcs:646 - Discrete Mathematics & Theoretical Computer Science, March 17, 2016, Vol. 18 no. 3 - https://doi.org/10.46298/dmtcs.646
The Flip Diameter of Rectangulations and Convex Subdivisions

Authors: Eyal Ackerman ; Michelle M. Allen ; Gill Barequet ; Maarten Löffler ; Joshua Mermelstein ; Diane L. Souvaine ; Csaba D. Tóth

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.


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

Consultation statistics

This page has been seen 530 times.
This article's PDF has been downloaded 468 times.