Constructing binary space partitions for orthogonal rectangles in practice


Conference Paper

In this paper, we develop a simple technique for constructing a Binary Space Partition (BSP) for a set of orthogonal rectangles in ℝ3. 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. © Springer-Verlag Berlin Heidelberg 1998.

Full Text

Duke Authors

Cited Authors

  • Murali, TM; Agarwal, PK; Vitter, JS

Published Date

  • January 1, 1998

Published In

Volume / Issue

  • 1461 LNCS /

Start / End Page

  • 211 - 222

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 10 (ISBN-10)

  • 3540648488

International Standard Book Number 13 (ISBN-13)

  • 9783540648482

Digital Object Identifier (DOI)

  • 10.1007/3-540-68530-8_18

Citation Source

  • Scopus