ATTENTION: The software behind KU ScholarWorks is being upgraded to a new version. Starting July 15th, users will not be able to log in to the system, add items, nor make any changes until the new version is in place at the end of July. Searching for articles and opening files will continue to work while the system is being updated.
If you have any questions, please contact Marianne Reed at mreed@ku.edu .
Constructing Binary Space Partitions for Orthogonal Rectangles in Practice
dc.contributor.author | Murali, T. M. | |
dc.contributor.author | Agarwal, Pankaj K. | |
dc.contributor.author | Vitter, Jeffrey Scott | |
dc.date.accessioned | 2011-03-21T20:30:12Z | |
dc.date.available | 2011-03-21T20:30:12Z | |
dc.date.issued | 1998 | |
dc.identifier.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 | |
dc.identifier.uri | http://hdl.handle.net/1808/7226 | |
dc.description | The original publication is available at www.springerlink.com | |
dc.description.abstract | 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. | |
dc.language.iso | en_US | |
dc.publisher | Springer Verlag | |
dc.title | Constructing Binary Space Partitions for Orthogonal Rectangles in Practice | |
dc.type | Article | |
kusw.kuauthor | Vitter, Jeffrey Scott | |
kusw.oastatus | fullparticipation | |
dc.identifier.doi | 10.1007/3-540-68530-8_18 | |
kusw.oaversion | Scholarly/refereed, author accepted manuscript | |
kusw.oapolicy | This item meets KU Open Access policy criteria. | |
dc.rights.accessrights | openAccess |