On Rectilinear Partitions with Minimum Stabbing Number

Let

S

be a set of

n

points in

${\Bbb R}^d$

, and let

r

be a parameter with 1 ≤ 

r

 ≤ 

n

. A rectilinear

r

-partition for

S

is a collection Ψ(

S

) : = {(

S

1

,

b

1

),…,(

S

t

,

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

/2

r

 ≤ |

S

i

| ≤ 2

n

/

r

for all 1 ≤ 

i

 ≤ 

t

. The (rectilinear) stabbing number of Ψ(

S

) is the maximum number of bounding boxes in Ψ(

S

) that are intersected by an axis-parallel hyperplane

h

. We study the problem of finding an optimal rectilinear

r

-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 already in

${\Bbb R}^2$

.

There are point sets such that any partition with disjoint bounding boxes has stabbing number Ω(

r

1 − 1/

d

), while the optimal partition has stabbing number 2.

An exact algorithm to compute optimal partitions, running in polynomial time if

r

is a constant, and a faster 2-approximation algorithm.

An experimental investigation of various heuristics for computing rectilinear

r

-partitions in

${\Bbb R}^2$

.