2017
Packing boundary-anchored rectangles
Publication
Publication
Presented at the
29th Canadian Conference on Computational Geometry, CCCG 2017 (July 2017), Ottawa
In this paper, we study the boundary-anchored rectangle packing problem in which we are given a set P of points on the boundary of an axis-aligned square Q. The goal is to find a set of disjoint axis-aligned rectangles in Q such that each rectangle is anchored at some point in P, each point in P is used to anchor at most one rectangle, and the total area of the rectangles is maximized. We show how to solve this problem in linear-time in the number of points of P, provided that the points of P are given in sorted order along the boundary of Q. The solvability of the general version of this problem, in which the points of P can also lie in the interior of Q, in polynomial time, is still open.
Additional Metadata | |
---|---|
29th Canadian Conference on Computational Geometry, CCCG 2017 | |
Organisation | Computational Geometry Lab |
Biedl, T. (Therese), Biniaz, A. (Ahmad), Maheshwari, A, & Mehrabi, S. (Saeed). (2017). Packing boundary-anchored rectangles. In CCCG 2017 - 29th Canadian Conference on Computational Geometry, Proceedings (pp. 138–143).
|