The Flip Diameter of Rectangulations and Convex Subdivisions

Eyal Ackerman; Michelle Allen; Gill Barequet; Maarten Löffler; Joshua Mermelstein; Diane Souvaine; Csaba Tóth

The Flip Diameter of Rectangulations and Convex Subdivisions

Eyal Ackerman, Michelle Allen, Gill Barequet, Maarten Löffler, Joshua Mermelstein, Diane Souvaine, Csaba Tóth

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We study the configuration space of rectanulations and convex subdivisions of $n$ points in the plane. It is shown that a sequence of $O(nlog 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 $n)$ operations are sufficient and necessary for others. Some of our bounds generalize to convex subdivisions of $n$ points in the plane.

Original language	English
Title of host publication	Proc. 11th Latin American Symposium on Theoretical Informatics
Publication status	Published - 2014

Bibliographical note

(to appear)

Keywords

CG, GRAPH

Cite this

@inproceedings{96b34d972d4b4e2a9bac6a3a3a85483d,

title = "The Flip Diameter of Rectangulations and Convex Subdivisions",

abstract = "We study the configuration space of rectanulations and convex subdivisions of $n$ points in the plane. It is shown that a sequence of $O(nlog 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 $n)$ operations are sufficient and necessary for others. Some of our bounds generalize to convex subdivisions of $n$ points in the plane.",

keywords = "CG, GRAPH",

author = "Eyal Ackerman and Michelle Allen and Gill Barequet and Maarten L{\"o}ffler and Joshua Mermelstein and Diane Souvaine and Csaba T{\'o}th",

note = "(to appear)",

year = "2014",

language = "English",

booktitle = "Proc. 11th Latin American Symposium on Theoretical Informatics",

}

TY - GEN

T1 - The Flip Diameter of Rectangulations and Convex Subdivisions

AU - Ackerman, Eyal

AU - Allen, Michelle

AU - Barequet, Gill

AU - Löffler, Maarten

AU - Mermelstein, Joshua

AU - Souvaine, Diane

AU - Tóth, Csaba

N1 - (to appear)

PY - 2014

Y1 - 2014

N2 - We study the configuration space of rectanulations and convex subdivisions of $n$ points in the plane. It is shown that a sequence of $O(nlog 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 $n)$ operations are sufficient and necessary for others. Some of our bounds generalize to convex subdivisions of $n$ points in the plane.

AB - We study the configuration space of rectanulations and convex subdivisions of $n$ points in the plane. It is shown that a sequence of $O(nlog 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 $n)$ operations are sufficient and necessary for others. Some of our bounds generalize to convex subdivisions of $n$ points in the plane.

KW - CG, GRAPH

M3 - Conference contribution

BT - Proc. 11th Latin American Symposium on Theoretical Informatics

ER -

The Flip Diameter of Rectangulations and Convex Subdivisions

Abstract

Bibliographical note

Keywords

Fingerprint

Cite this