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). |