Advanced

Box-trees and R-trees with near-optimal query time

Agarwal, PK; de Berg, M; Gudmundsson, J; Hammar, Mikael LU and Haverkort, HJ (2002) In Discrete & Computational Geometry 28(3). p.291-312
Abstract
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.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Discrete & Computational Geometry
volume
28
issue
3
pages
291 - 312
publisher
Springer
external identifiers
  • wos:000177922200002
  • scopus:0036026076
ISSN
0179-5376
DOI
10.1007/s00454-002-2817-1
language
English
LU publication?
yes
id
ba31b3ae-6460-4526-a38c-6a3b02026f01 (old id 329254)
date added to LUP
2007-08-03 12:24:37
date last changed
2017-01-01 07:24:53
@article{ba31b3ae-6460-4526-a38c-6a3b02026f01,
  abstract     = {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.},
  author       = {Agarwal, PK and de Berg, M and Gudmundsson, J and Hammar, Mikael and Haverkort, HJ},
  issn         = {0179-5376},
  language     = {eng},
  number       = {3},
  pages        = {291--312},
  publisher    = {Springer},
  series       = {Discrete & Computational Geometry},
  title        = {Box-trees and R-trees with near-optimal query time},
  url          = {http://dx.doi.org/10.1007/s00454-002-2817-1},
  volume       = {28},
  year         = {2002},
}