COVERING A POINT SET BY TWO DISJOINT RECTANGLES
Sang-Sub Kim, Sang Won Bae, Hee-Kap Ahn · International Journal of Computational Geometry & Applications · 2011
Given a set S of n points in the plane, the disjoint two-rectangle covering problem is to find a pair of disjoint rectangles such that their union contains S and the area of the larger rectangle is minimized. In this paper we consider two variants of this optimization problem: (1) the rectangles are allowed to be reoriented freely while restricting them to be parallel to each other, and (2) one rectangle is restricted to be axis-parallel but the other rectangle is allowed to be reoriented freely. For both of the problems, we present O(n2 log n)-time algorithms using O(n) space.