Constructing Binary Space Partitions for Orthogonal Rectangles in Practice

T. M. Murali, P. K. Agarwal, and J. S. Vitter. ``Constructing Binary Space Partitions for Orthogonal Rectangles in Practice,'' Proceedings of the 6th Annual European Symposium on Algorithms (ESA '98), Venice, August 1998, published in Lecture Notes in Computer Science, 1461, Springer-Verlag, Berlin, 211-222.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

In this paper, we develop a simple technique for constructing a Binary Space Partition (BSP) for a set of orthogonal rectangles in three-dimensions. Our algorithm has the novel feature that it tunes its performance to the geometric properties of the rectangles, e.g., their aspect ratios. We have implemented our algorithm and tested its performance on real data sets. We have also systematically compared the performance of our algorithm with that of other techniques presented in the literature. Our studies show that our algorithm constructs BSPs of near-linear size and small height in practice, has fast running times, and answers queries efficiently. It is a method of choice for constructing BSPs for orthogonal rectangles.