On Optimal Cuts of Hyperrectangles

We are given a set of n d-dimensional (possibly intersecting) isothetic hyperrectangles. The topic of this paper is the separation of these rectangles by means of a cutting isothetic hyperplane. Thereby we assume that a rectangle which is intersected by the cutting plane is cut into two non-overlapping hyperrectangles. We investigate the behavior of several kinds of balancing functions, as well as their linear combination and present optimal and practical algorithms for computing the corresponding balanced cuts. In addition, we give tight worst-case bounds for the quality of the balanced cuts. Our results include a generalization [1] and a simplification [3, 10] of recent results. Keywords: rectangles, balanced cuts, separation, binary space partition 1 Introduction Given a set of n d-dimensional (possibly intersecting) isothetic hyperrectangles, we consider the problem of separating these rectangles by means of a cutting isothetic hyperplane. If the cutting plane crosses a rectangle,..