Binary Space Partitions for Axis-Parallel Segments, Rectangles, and Hyperrectangles

We provide a variety of new upper and lower bounds and simpler proof techniques for the efficient construction of binary space partitions (BSPs) of axis- parallel rectangles of various dimensions, (a) We construct a set of n disjoint axis-parallel segments in the plane such that any binary space auto-partition has size at least 2n - o(n), almost matching an upper bound of d'Amore and Franciosa. (b) We establish a similar lower bound of 7n/3 - o(n) for disjoint rectangles in the plane, (c) We simplify and improve BSP constructions of Paterson and Yao for disjoint segments in ℝ^d and disjoint rectangles in ℝ³. (d) We derive a worst-case bound of θ(n^5/3) for the size of BSPs of disjoint 2-rectangles in 4-space, (e) For disjoint k-rectangles in d-space, we prove the worst-case bound θ(n^d/(d-k)), for any k < d/2 this bound holds for all k < d if the rectangles are allowed to intersect.