DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2016.13

Anchored Rectangle and Square Packings

Authors: Kevin Balas, Adrian Dumitrescu, and Csaba Tóth

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract

For points p_1,...,p_n in the unit square [0,1]^2, an anchored rectangle packing consists of interior-disjoint axis-aligned empty rectangles r_1,...,r_n in [0,1]^2 such that point p_i is a corner of the rectangle r_i (that is, r_i is anchored at p_i) for i=1,...,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 n, there are point sets for which the area of every anchored rectangle packing is at most 2/3. The maximum area of an anchored 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 -epsilon for rectangles and 5/32 for squares, for computing anchored packings of maximum area in O(n log n) 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/epsilon)} and exp(poly(log (n/epsilon))) time, respectively.

Cite as

Kevin Balas, Adrian Dumitrescu, and Csaba Tóth. Anchored Rectangle and Square Packings. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{balas_et_al:LIPIcs.SoCG.2016.13,
  author =	{Balas, Kevin and Dumitrescu, Adrian and T\'{o}th, Csaba},
  title =	{{Anchored Rectangle and Square Packings}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.13},
  URN =		{urn:nbn:de:0030-drops-59054},
  doi =		{10.4230/LIPIcs.SoCG.2016.13},
  annote =	{Keywords: Rectangle packing, anchored rectangle, greedy algorithm, charging scheme, approximation algorithm.}
}

Search Results

Documents authored by Balas, Kevin

Anchored Rectangle and Square Packings

Abstract

Cite as

Thanks for your feedback!

Could not send message