ON OPTIMAL CUTS OF HYPERRECTANGLES

We are given a set of n d-dimensional (possibly intersecting) isotheti c hyperrectangles. The topic of this paper is the separation of these rectangles by means of a cutting isothetic hyperplane. Thereby we assu me that a rectangle which is intersected by the cutting plane iscut in to two non-overlapping hyperrectangles. We investigate the behavior of several kinds of balancing functions, as well as their linear combina tion and present optimal and practical algorithms for computing the co rresponding balanced cuts. In addition, we give tight worst-case bound s for the quality of the balanced cuts.