The Library
Combinatorial generation via permutation languages. III. Rectangulations
Tools
Merino, Arturo and Mutze, Torsten (2023) Combinatorial generation via permutation languages. III. Rectangulations. Discrete & Computational Geometry, 70 . pp. 51-122. doi:10.1007/s00454-022-00393-w ISSN 0179-5376.
|
PDF
WRAP-Combinatorial-generation-via-permutation-languages-III-Rectangulations-Mutze-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (2106Kb) | Preview |
Official URL: https://doi.org/10.1007/s00454-022-00393-w
Abstract
A generic rectangulation is a partition of a rectangle into finitely many interior-disjoint rectangles, such that no four rectangles meet in a point. In this work we present a versatile algorithmic framework for exhaustively generating a large variety of different classes of generic rectangulations. Our algorithms work under very mild assumptions, and apply to a large number of rectangulation classes known from the literature, such as generic rectangulations, diagonal rectangulations, 1-sided/area-universal, block-aligned rectangulations, and their guillotine variants, including aspect-ratio-universal rectangulations. They also apply to classes of rectangulations that are characterized by avoiding certain patterns, and in this work we initiate a systematic investigation of pattern avoidance in rectangulations. Our generation algorithms are efficient, in some cases even loopless or constant amortized time, i.e., each new rectangulation is generated in constant time in the worst case or on average, respectively. Moreover, the Gray codes we obtain are cyclic, and sometimes provably optimal, in the sense that they correspond to a Hamilton cycle on the skeleton of an underlying polytope. These results are obtained by encoding rectangulations as permutations, and by applying our recently developed permutation language framework.
Item Type: | Journal Article | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||||||
Library of Congress Subject Headings (LCSH): | Combinatorial analysis, Combinatorial geometry, Probabilities, Graph theory | ||||||||||||
Journal or Publication Title: | Discrete & Computational Geometry | ||||||||||||
Publisher: | Springer New York LLC | ||||||||||||
ISSN: | 0179-5376 | ||||||||||||
Official Date: | July 2023 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 70 | ||||||||||||
Page Range: | pp. 51-122 | ||||||||||||
DOI: | 10.1007/s00454-022-00393-w | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
Date of first compliant deposit: | 6 January 2022 | ||||||||||||
Date of first compliant Open Access: | 7 November 2022 | ||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||
Related URLs: | |||||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year