Options
On greedily packing anchored rectangles
Publikationstyp
Conference Paper
Date Issued
2021-07
Sprache
English
Author(s)
First published in
Number in series
198
Article Number
61
Citation
48th International Colloquium on Automata, Languages, and Programming : ICALP 2021, July 12-16, 2021, Glasgow, Scotland (virtual conference) . - (Leibniz International Proceedings in Informatics, LIPIcs ; vol. 198). - Art. no. 61 (2021)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH
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 [18] posed this problem in 1969, asking whether one can always cover at least 50% of U. Over 40 years later, Dumitrescu and Tóth [12] 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.
Subjects
Charging scheme
Greedy algorithm
Lower-left anchored rectangle packing
DDC Class
004: Informatik