License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.61
URN: urn:nbn:de:0030-drops-141306
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14130/
Go to the corresponding LIPIcs Volume Portal

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

On Greedily Packing Anchored Rectangles

pdf-format:
LIPIcs-ICALP-2021-61.pdf (2 MB)

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.

BibTeX - Entry

@InProceedings{damerius_et_al:LIPIcs.ICALP.2021.61,
  author =	{Damerius, Christoph and Kaaser, Dominik and Kling, Peter and Schneider, Florian},
  title =	{{On Greedily Packing Anchored Rectangles}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{61:1--61:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14130},
  URN =		{urn:nbn:de:0030-drops-141306},
  doi =		{10.4230/LIPIcs.ICALP.2021.61},
  annote =	{Keywords: lower-left anchored rectangle packing, greedy algorithm, charging scheme}
}

Keywords: lower-left anchored rectangle packing, greedy algorithm, charging scheme
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI