Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
; ; ; and
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
2016-04-01 17:07:25
date last changed
2025-10-14 13:30:18
@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}},
  doi          = {{10.1007/s00454-002-2817-1}},
  volume       = {{28}},
  year         = {{2002}},
}