Few sequence pairs suffice: representing all rectangle placements

DOI10.1137/19M1246456MaRDI QIDQ5128501zbMATH OpenFDO

Authors Jannik Silvanus, Jens Vygen

Publication date 27 October 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.09779

zbMATH Keywords

plane permutationsrectangle placementssequence pairs

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Abstract: We consider representations of general non-overlapping placements of rectangles by spatial relations (west, south, east, north) of pairs of rectangles. We call a set of representations complete if it contains a representation of every placement of $n$ rectangles. We prove a new upper bound of $mathcalO(fracn!n^{6}cdot(frac11+5sqrt52{)}^n)$ and a new lower bound of $Omega(fracn!n^{4}cdot(4+2sqrt2{)}^n)$ on the minimum cardinality of complete sets of representations. A key concept in the proofs of these results are pattern-avoiding permutations. The new upper bound directly improves upon the well-known sequence pair representation, which has size $(n!{)}^2$, by only considering a restricted set of sequence pairs. It implies theoretically faster algorithms for VLSI placement problems.

Recommendations

• Denser packings obtained in O(n n) time
• Computational Science – ICCS 2005
• An optimal algorithm for rectangle placement
• New perspectives in VLSI design automation: deterministic packing by sequence pair
• Permutation layout

Cites work

• A bijection between permutations and floorplans, and its applications
• Forest-like permutations
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• Orders induced by segments in floorplans and (2-14-3, 3-41-2)-avoiding permutations
• Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence

Cited in

(1)

• Computational Science – ICCS 2005

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Few sequence pairs suffice: representing all rectangle placements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5128501)