Packing boundary-anchored rectangles
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.
|Conference||29th Canadian Conference on Computational Geometry, CCCG 2017|
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).