On Greedily Packing Anchored Rectangles

Authors Christoph Damerius, Dominik Kaaser , Peter Kling , Florian Schneider



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.61.pdf
  • Filesize: 1.62 MB
  • 20 pages

Document Identifiers

Author Details

Christoph Damerius
  • University of Hamburg, Germany
Dominik Kaaser
  • University of Hamburg, Germany
Peter Kling
  • University of Hamburg, Germany
Florian Schneider
  • University of Hamburg, Germany

Cite AsGet BibTex

Christoph Damerius, Dominik Kaaser, Peter Kling, and Florian Schneider. On Greedily Packing Anchored Rectangles. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 61:1-61:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.61

Abstract

Consider a set P of points in the unit square U = [1,0), one of them being the origin. For each point p ∈ P you may draw an axis-aligned rectangle in U with its lower-left corner being p. What is the maximum area such rectangles can cover without overlapping each other? Freedman posed this problem in 1969, asking whether one can always cover at least 50% of U. Over 40 years later, Dumitrescu and Tóth [Adrian Dumitrescu and Csaba D. Tóth, 2015] achieved the first constant coverage of 9.1%; since then, no significant progress was made. While 9.1% might seem low, the authors could not find any instance where their algorithm covers less than 50%, nourishing the hope to eventually prove a 50% bound. While we indeed significantly raise the algorithm’s coverage to 39%, we extinguish the hope of reaching 50% by giving points for which its coverage stays below 43.3%. Our analysis studies the algorithm’s average and worst-case density of so-called tiles, which represent the staircase polygons in which a point can freely choose its maximum-area rectangle. Our approach is comparatively general and may potentially help in analyzing related algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • lower-left anchored rectangle packing
  • greedy algorithm
  • charging scheme

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Anna Adamaszek, Parinya Chalermsook, and Andreas Wiese. How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 43-60, 2015. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.43.
  2. Anna Adamaszek and Andreas Wiese. Approximation Schemes for Maximum Weight Independent Set of Rectangles. In 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 400-409, 2013. URL: https://doi.org/10.1109/FOCS.2013.50.
  3. Anna Adamaszek and Andreas Wiese. A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1491-1505, 2015. URL: https://doi.org/10.1137/1.9781611973730.98.
  4. Hugo A. Akitaya, Matthew D. Jones, David Stalfa, and Csaba D. Tóth. Maximum Area Axis-Aligned Square Packings. In MFCS, pages 77:1-77:15, 2018. Google Scholar
  5. Antonios Antoniadis, Felix Biermeier, Andrés Cristi, Christoph Damerius, Ruben Hoeksma, Dominik Kaaser, Peter Kling, and Lukas Nölke. On the Complexity of Anchored Rectangle Packing. In 27th Annual European Symposium on Algorithms (ESA), pages 8:1-8:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.8.
  6. Kevin Balas, Adrian Dumitrescu, and Csaba D. Tóth. Anchored rectangle and square packings. Discret. Optim., 26:131-162, 2017. URL: https://doi.org/10.1016/j.disopt.2017.08.003.
  7. Kevin Balas and Csaba D. Tóth. On the number of anchored rectangle packings for a planar point set. Theor. Comput. Sci., 654:143-154, 2016. URL: https://doi.org/10.1016/j.tcs.2016.03.007.
  8. Vincent Bian. Special Configurations in Anchored Rectangle Packings, 2018. URL: http://arxiv.org/abs/1809.01769.
  9. Therese C. Biedl, Ahmad Biniaz, Anil Maheshwari, and Saeed Mehrabi. Packing boundary-anchored rectangles and squares. Comput. Geom., 88:101610, 2020. URL: https://doi.org/10.1016/j.comgeo.2020.101610.
  10. Timothy M. Chan and Sariel Har-Peled. Approximation Algorithms for Maximum Independent Set of Pseudo-Disks. Discret. Comput. Geom., 48(2):373-392, 2012. URL: https://doi.org/10.1007/s00454-012-9417-5.
  11. Christoph Damerius, Dominik Kaaser, Peter Kling, and Florian Schneider. On greedily packing anchored rectangles. CoRR, abs/2102.08181, 2021. URL: http://arxiv.org/abs/2102.08181.
  12. Adrian Dumitrescu and Csaba D. Tóth. Packing anchored rectangles. Comb., 35(1):39-61, 2015. URL: https://doi.org/10.1007/s00493-015-3006-1.
  13. Ruben Hoeksma and Matthew Maat. A better lower bound for Lower-Left Anchored Rectangle Packing. CoRR, abs/2102.05747, 2021. URL: http://arxiv.org/abs/2102.05747.
  14. IBM. Ponder This Challenge: Puzzle for June 2004, 2004. URL: https://www.research.ibm.com/haifa/ponderthis/challenges/June2004.html.
  15. Klaus Jansen and Malin Rau. Improved approximation for two dimensional strip packing with polynomial bounded width. Theor. Comput. Sci., 789:34-49, 2019. URL: https://doi.org/10.1016/j.tcs.2019.04.002.
  16. Konstantinos G. Kakoulis and Ioannis G. Tollis. Labeling Algorithms. In Roberto Tamassia, editor, Handbook on Graph Drawing and Visualization, pages 489-515. Chapman and Hall/CRC, 2013. Google Scholar
  17. Arturo I. Merino and Andreas Wiese. On the Two-Dimensional Knapsack Problem for Convex Polygons. In 47th International Colloquium on Automata, Languages, and Programming, (ICALP), pages 84:1-84:16, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.84.
  18. William Thomas Tutte, editor. Recent Progress in Combinatorics: Proceedings of the 3rd Waterloo Conference on Combinatorics. Academic Press, 1969. Google Scholar
  19. Peter Winkler. Packing Rectangles. Mathematical Mind-Benders, pages 133-134, 2007. Google Scholar
  20. Peter Winkler. Puzzled: Rectangles Galore. Commun. ACM, 53(11):112, 2010. URL: https://doi.org/10.1145/1839676.1839700.
  21. Peter Winkler. Puzzled: Solutions and Sources. Commun. ACM, 53(9):110, 2010. URL: https://doi.org/10.1145/1810891.1810917.
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