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