On optimal guillotine partitions approximating optimal d-box partitions

AbstractGiven a set of n points, P, in Ed (the plane when d = 2) that lie inside a d-box (rectangle when d = 2) R, we study the problem of partitioning R into d-boxes by introducing a set of orthogonal hyperplane segments (line segments when d = 2) whose total (d − 1)-volume (length when d = 2) is the least possible. In a valid d-box partition, each point in P must be included in at least one partitioning orthogonal hyperplane segment. Since this minimization problem is NP-hard and thus likely to be computationally intractable, we present an approximation algorithm to generate a suboptimal solution. This solution is obtained by finding an optimal guillotine partition, i.e., a special type of rectangular partition, which can be generated in O(dn2d+1) time. We present a simple proof that the (d − 1)-volume of an optimal guillotine partition is not greater than 2d − 4 + 4/d times the (d − 1)-volume of an optimal d-box partition