AN EFFICIENT DIVIDE-AND-CONQUER APPROXIMATION ALGORITHM FOR PARTITIONING INTO D-BOXES

Let P be a set of n points located inside a d-box (rectangle if d=2) R. We study the problem of partitioning R into d-boxes by introducing a set of hyperplane (line if d=2) segments of least total (d-1)–volume (length if d=2). Each of the resulting d-boxes in a valid partition cannot contain points from P as interior points. Since this problem is computationally intractable (NP-hard) even when d=2, we present an efficient approximation algorithm for its solution. The partition generated by our approximation algorithm is guaranteed to be within 2d times the optimal solution value. We also present a problem instance for each d≥2 for which the approximation bound is tight for the algorithm. The time complexity for our algorithm is O(dn log n).