Box-trees and R-trees with near-optimal query time
Published
Journal Article
A box-tree is a bounding-volume hierarchy that uses axis-aligned boxes as bounding volumes. The query complexity of a box-tree with respect to a given type of query is the maximum number of nodes visited when answering such a query. We describe several new algorithms for constructing box-trees with small worst-case query complexity with respect to queries with axis-parallel boxes and with points. We also prove lower bounds on the worst-case query complexity for box-trees, which show that our results are optimal or close to optimal. Finally, we present algorithms to convert box-trees to R-trees, resulting in R-trees with (almost) optimal query complexity.
Full Text
Duke Authors
Cited Authors
- Agarwal, PK; De Berg, M; Gudmundsson, J; Hammar, M; Haverkort, HJ
Published Date
- January 1, 2002
Published In
Volume / Issue
- 28 / 3
Start / End Page
- 291 - 312
International Standard Serial Number (ISSN)
- 0179-5376
Digital Object Identifier (DOI)
- 10.1007/s00454-002-2817-1
Citation Source
- Scopus