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 SubdivisionsArticle

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
    Funding:
      Source : OpenAIRE Graph
    • Geometric Data Imprecision in Realistic Settings; Funder: Netherlands Organisation for Scientific Research (NWO); Code: 639.021.123
    • Geometric Data Structures; Funder: National Science Foundation; Code: 0830734

    Consultation statistics

    This page has been seen 905 times.
    This article's PDF has been downloaded 683 times.