Akitaya, Hugo A.
[VerfasserIn];
Jones, Matthew D.
[VerfasserIn];
Stalfa, David
[VerfasserIn];
Tóth, Csaba D.
[VerfasserIn]
;
Hugo A. Akitaya and Matthew D. Jones and David Stalfa and Csaba D. Tóth
[MitwirkendeR]
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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.