Box-trees and R-trees with near-optimal query time
(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:
https://lup.lub.lu.se/record/329254
- author
- Agarwal, PK ; de Berg, M ; Gudmundsson, J ; Hammar, Mikael LU and Haverkort, HJ
- organization
- publishing date
- 2002
- 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
- 2022-01-29 00:33:44
@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}}, }