Practical techniques for constructing Binary Space Partitions for orthogonal rectangles


Journal Article

We present the first systematic comparison of the performance of algorithms that construct Binary Space Partitions for orthogonal rectangles in R3. We compare known algorithms with our implementation of a variant of a recent algorithm of Agarwal et al.. We show via an empirical study that their algorithm constructs BSPs of near-linear size in practice and performs better than most of the other algorithms in the literature.

Full Text

Duke Authors

Cited Authors

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

Published Date

  • January 1, 1997

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 382 - 384

Digital Object Identifier (DOI)

  • 10.1145/262839.263011

Citation Source

  • Scopus