Technical Report No. 35, August 1991 - Abstract

Bruno Becker, Paolo Giulio Franciosa, Stephan Gschwind, Thomas Ohler, Gerald Thiemt, Peter Widmayer:
An Optimal Algorithm for Approximating a Set of Rectangles by Two Minimum Area Rectangles

In this paper we face the problem of computing a conservative approximation of a set of isothetic rectangles in the plane by means of a pair of enclosing isothetic rectangles. We propose an O(n*log n) time algorithm for finding, given a set M of n isothetic rectangles, a pair of isothetic rectangles (s,t) such that s and t enclose all rectangles of M and area(s) + area(t) is minimal. Moreover we prove an O(n*log n) lower bound for the one-dimensional version of the problem.