Binary Space Partitions for Fat Rectangles

P. K. Agarwal, E. F. Grove, T. M. Murali, and J. S. Vitter. ``Binary Space Partitions for Fat Rectangles,'' SIAM Journal on Computing, 29(5), 2000, 1422-1448. A shortened version appeared earlier in the Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS'96), Burlington, Vermont, October 1996.

Full text (Adobe pdf format)

We consider the practical problem of constructing binary space partitions (BSPs) for a set S of n orthogonal, non-intersecting, two-dimensional rectangles in three-dimensional Euclidean space such that the aspect ratio of each rectangle in S is at most $\alpha$, for some constant $\alpha \geq 1$. We present an  $O(n 2^{\sqrt{\log n}})$-time algorithm to build a binary space partition of size $O(n 2^{\sqrt{\log n}})$for S. We also show that if m of the n rectangles in S have aspect ratios greater than $\alpha$, we can construct a BSP of size  $O(n \sqrt{m} 2^{\sqrt{\log n}})$ for S in $O(n \sqrt{m} 2^{\sqrt{\log n}})$ time. The constants of proportionality in the big-oh terms are linear in $\log \alpha$. We extend these results to cases in which the input contains non-orthogonal or intersecting objects.