1 Search Results for "Schneider, Florian"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.61
On Greedily Packing Anchored Rectangles

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

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

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.
Cite as

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)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.61},
  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}
}
  • Refine by Author
  • 1 Damerius, Christoph
  • 1 Kaaser, Dominik
  • 1 Kling, Peter
  • 1 Schneider, Florian

  • Refine by Classification
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 charging scheme
  • 1 greedy algorithm
  • 1 lower-left anchored rectangle packing

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact