Constructing Binary Space Partitions for Orthogonal Rectangles in Practice
Issue Date
1998Author
Murali, T. M.
Agarwal, Pankaj K.
Vitter, Jeffrey Scott
Publisher
Springer Verlag
Type
Article
Article Version
Scholarly/refereed, author accepted manuscript
Metadata
Show full item recordAbstract
In this paper, we develop a simple technique for constructing
a I3inary Space Partition (nSP) for a set of orthogonal rectangles in IR3.
OUf algorithm has the novel feature that it tunes its performance to the
geometric properties of the rectangles, e.g., their aspect ratios.
"Fe have implemented our algorithm and tested its performance on real
data scti). V\.Tc 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 nsps 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.
Description
The original publication is available at www.springerlink.com
Collections
Citation
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, Berlin, Germany, 211–222. http://dx.doi.org/10.1007/3-540-68530-8_18
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.