Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles
Adrian Dumitrescu, Joseph S. Mitchell, Micha Sharir · 2001
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 \cite{dAF} 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 $\frac{9}{4}n-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 axis-parallel segments in higher dimensions, simplifying the technique of \cite{PY2} and improving the constants. (d) We obtain an alternative construction (to that in \cite{PY2}) 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 $\reals^4$, and give a matching worst-case lower bound of $\Omega(n^{5/3})$ for the size of such a BSP. (f) We extend the results of \cite{PY2} to axis-parallel $k$-dimensional rectangles in $\reals^d$, for $k