The Flip Diameter of Rectangulations and Convex Subdivisions

We study the configuration space of rectangulations and convex subdivisions of nn points in the plane. It is shown that a sequence of O(nlogn)O(nlog⁡n) elementary flip and rotate operations can transform any rectangulation to any other rectangulation on the same set of nn points. This bound is the b...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2016-11, Vol.18 (3)
Main Authors: Ackerman, Eyal, Allen, Michelle M, Barequet, Gill, Löffler, Maarten, Mermelstein, Joshua, Souvaine, Diane L, Tóth, Csaba D
Format: Article
Language:English
Subjects:
Subdivisions
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the configuration space of rectangulations and convex subdivisions of nn points in the plane. It is shown that a sequence of O(nlogn)O(nlog⁡n) elementary flip and rotate operations can transform any rectangulation to any other rectangulation on the same set of nn points. This bound is the best possible for some point sets, while Θ(n)Θ(n) operations are sufficient and necessary for others. Some of our bounds generalize to convex subdivisions of nn points in the plane.
ISSN:1365-8050