Enclosing a set of objects by two minimum area rectangles

In this paper, we face the problem of computing an enclosing pair of axis-parallel rectangles of a set of polygonal objects in the plane, serving as a simple container. We propose an O(n alpha(n)log n) worst-case time algorithm, where alpha() is the inverse Ackermann's function, for finding, given a set M of points, segments and polygons defined by n vertices, a pair of axis-parallel rectangles (s,t) such that s boolean OR t encloses all objects in M and area(s) + area(t) is minimum. The algorithm works in O(n alpha (n) log log n) worst-case space. Moreover, we prove an Omega(n log n) lower bound for the one-dimensional version of the problem. We also show that for the special case of enclosing a set of polygons with axis-parallel sides, our algorithm runs in optimal worst-case time O(n log n), using worst-case space O(n log log n). (C) 1996 Academic Press, Inc.