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(dn log n + d
2
n
2d– 1) algorithm for finding an optimal solution.
Keywords computational geometry - covering problems - axis-parallel rectangles
Partially supported by grant Wi810/2-5 of the Deutsche Forschungsgemeinschaft DFG, and by the ESPRIT II BRA Project 3075 ALCOM of the European Community.
Work done while the author was partially supported by Istituto di Analisi dei Sistemi ed Informatica, CNR, Viale Manzoni 30, I-00185 Roma, Italy