Technical Report No. 36, August 1991 - Abstract

Bruno Becker, Paolo Giulio Franciosa, Stephan Gschwind, Thomas Ohler, Gerald Thiemt, Peter Widmayer:
Enclosing Many Boxes by an Optimal Pair of Boxes

We look at the problem: Given a set M of n d-dimensional intervals, find two d-dimensional intervals S, T, such that all intervals in M are enclosed by S or by T, the distribution is balanced and the intervals S and T fulfill a geometric criterion, e.g. like minimum area sum.Up to now no polynomial time algorithm was known for that problem. We present an O(d*n*log n) + d^2*n^(2d-1)) algorithm for finding an optimal solution.