Anchored rectangle and square packings

DOI10.4230/LIPICS.SOCG.2016.13MaRDI QIDQ3132846zbMATHOpenAlexFDO

Authors Kevin Balas, Adrian Dumitrescu, Csaba D. Tóth

Publication date 30 January 2018

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

zbMATH Keywords

approximation algorithmgreedy algorithmrectangle packingcharging schemeanchored rectangle

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: For points $p_1,ldots,p_n$ in the unit square $[0,1{]}^2$, an emph{anchored rectangle packing} consists of interior-disjoint axis-aligned empty rectangles $r_1,ldots,r_{n}subseteq[0,1{]}^2$ such that point $p_i$ is a corner of the rectangle $r_i$ (that is, $r_i$ is emph{anchored} at $p_i$) for $i=1,ldots,n$. We show that for every set of $n$ points in $[0,1{]}^2$, there is an anchored rectangle packing of area at least $7/12-O(1/n)$, and for every $ninmathbfN$, there are point sets for which the area of every anchored rectangle packing is at most $2/3$. The maximum area of an anchored emph{square} packing is always at least $5/32$ and sometimes at most $7/27$. The above constructive lower bounds immediately yield constant-factor approximations, of $7/12-varepsilon$ for rectangles and $5/32$ for squares, for computing anchored packings of maximum area in $O(nlogn)$ time. We prove that a simple greedy strategy achieves a $9/47$-approximation for anchored square packings, and $1/3$ for lower-left anchored square packings. Reductions to maximum weight independent set (MWIS) yield a QPTAS and a PTAS for anchored rectangle and square packings in $n^{O(1/varepsilon)}$ and $exp(mpoly(log(n/varepsilon)))$ time, respectively.

Recommendations

• Anchored rectangle and square packings
• Maximum area axis-aligned square packings
• Packing boundary-anchored rectangles and squares
• On the number of anchored rectangle packings for a planar point set

Cited in

(7)

• On the number of anchored rectangle packings for a planar point set
• The reach of axis-aligned squares in the plane
• On the number of anchored rectangle packings for a planar point set
• Anchored rectangle and square packings
• On the complexity of anchored rectangle packing
• Maximum area axis-aligned square packings
• Packing boundary-anchored rectangles and squares

This page was built for publication: Anchored rectangle and square packings

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