Binary space partitions for axis-parallel segments rectangles, and hyperrectangles

We provide a variety of new results, including upper and lower bounds, as well as simpler proof techniques for the efficient construction of binary space partitions (BSP's) of axis-parallel segments, rectangles, and hyperrectangles. (a) A consequence of the analysis in [1] is that any set of n axis-parallel and pairwise-disjoint line segments in the plane admits a binary space partition of size at most 2n - 1. We establish a worst-case lower bound of 2n - o(n) for the size of such a BSP, thus showing that this bound is almost tight in the worst case. (b) We give an improved worst-case lower bound of 9/4n - o(n) on the size of a BSP for isothetic pairwise disjoint rectangles. (c) We present simple methods, with equally simple analysis, for constructing BSP's for axisparallel segments in higher dimensions, simplifying the technique of [9] and improving the constants. (d) We obtain an alternative construction (to that in [9]) of BSP's for collections of axis-parallel rectangles in 3-space. (e) We present a construction of BSP's of size O(n^5/3) for n axis-parallel pairwise disjoint 2-rectangles in R⁴, and give a matching worstcase lower bound of Ω(n^5/3) for the size of such a BSP. (f) We extend the results of [9] to axis-parallel k-dimensional rectangles in R^d, for k < d/2, and obtain a worst-case tight bound of Θ(n^{d/(d - k)}) for the size of a BSP of n rectangles. Both upper and lower bounds also hold for d/2 ≤ k ≤ d - 1 if we allow the rectangles to intersect.