DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2018.77

Maximum Area Axis-Aligned Square Packings

Authors: Hugo A. Akitaya, Matthew D. Jones, David Stalfa, and Csaba D. Tóth

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract

Given a point set S={s_1,... , s_n} in the unit square U=[0,1]^2, an anchored square packing is a set of n interior-disjoint empty squares in U such that s_i is a corner of the ith square. The reach R(S) of S is the set of points that may be covered by such a packing, that is, the union of all empty squares anchored at points in S. It is shown that area(R(S))>= 1/2 for every finite set S subset U, and this bound is the best possible. The region R(S) can be computed in O(n log n) time. Finally, we prove that finding a maximum area anchored square packing is NP-complete. This is the first hardness proof for a geometric packing problem where the size of geometric objects in the packing is unrestricted.

Cite as

Hugo A. Akitaya, Matthew D. Jones, David Stalfa, and Csaba D. Tóth. Maximum Area Axis-Aligned Square Packings. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 77:1-77:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{akitaya_et_al:LIPIcs.MFCS.2018.77,
  author =	{Akitaya, Hugo A. and Jones, Matthew D. and Stalfa, David and T\'{o}th, Csaba D.},
  title =	{{Maximum Area Axis-Aligned Square Packings}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{77:1--77:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.77},
  URN =		{urn:nbn:de:0030-drops-96594},
  doi =		{10.4230/LIPIcs.MFCS.2018.77},
  annote =	{Keywords: square packing, geometric optimization}
}

Search Results

Documents authored by Jones, Matthew D.

Maximum Area Axis-Aligned Square Packings

Abstract

Cite as

Thanks for your feedback!

Could not send message