Anchored Rectangle and Square Packings

Authors Kevin Balas, Adrian Dumitrescu, Csaba Tóth



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.13.pdf
  • Filesize: 0.6 MB
  • 16 pages

Document Identifiers

Author Details

Kevin Balas
Adrian Dumitrescu
Csaba Tóth

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.SoCG.2016.13

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.
Keywords
  • Rectangle packing
  • anchored rectangle
  • greedy algorithm
  • charging scheme
  • approximation algorithm.

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail