On rectilinear partitions with minimum stabbing number

Let S be a set of n points in R^d, and let r be a parameter with 1 \leq r \leq n. A rectilinear partition for S is a collection \Psi S) := {(S_1, b_1), ..., (S_, b_t)} such that the sets S_i form a partition of S, each b_i is the bounding box of S_i, and n/2r \leq |S_i| \leq 2n/r for all 1 \leq i \leq t. The (rectilinear) stabbing number of \Psi (S) is the maximum, over all axis-parallel hyperplanes h, of the number of bounding boxes used in \Psi (S) that are intersected by h. We study the problem of finding an optimal rectilinear partition---a rectilinear partition with minimum stabbing number---for a given set S. We obtain the following results. * Computing an optimal partition is NP-hard. * There are point sets such that any partition with disjoint bounding boxes has stabbing number \Omega (r^(1 - 1/d)), while the optimal partition has stabbing number 2. * A 2-approximation algorithm for computing optimal partitions, running in polynomial time if r is a constant