Packing boundary-anchored rectangles and squares
Consider a set P of n points on the boundary of an axis-aligned square Q. We study the boundary-anchored packing problem on P in which the goal is to find a set of interior-disjoint axis-aligned rectangles in Q such that each rectangle is anchored (has a corner 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. Here, a rectangle is anchored at a point p in P if one of its corners coincides with p. In this paper, we show how to solve this problem in time linear in n, provided that the points of P are given in sorted order along the boundary of Q. We also consider the problem for anchoring squares and give an O(n4)-time algorithm when the points in P lie on two opposite sides of Q.
|Boundary-anchored packing, Rectangle packing, Square packing|
|Organisation||School of Computer Science|
Biedl, T. (Therese), Biniaz, A. (Ahmad), Maheshwari, A, & Mehrabi, S. (Saeed). (2020). Packing boundary-anchored rectangles and squares. Computational Geometry. doi:10.1016/j.comgeo.2020.101610