2026-07-23T04:54:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9659 2024-03-06T10:44:39Z ddc:004 open_access

Maximum Area Axis-Aligned Square Packings Akitaya, Hugo A. Jones, Matthew D. Stalfa, David Tóth, Csaba D. square packing geometric optimization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hugo A. Akitaya and Matthew D. Jones and David Stalfa and Csaba D. Tóth 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.77 urn:nbn:de:0030-drops-96594 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.77 eng https://creativecommons.org/licenses/by/3.0/legalcode