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

P.K. Agarwal; M. Berg, de; J. Gudmundsson; M. Hammar; H.J. Haverkort

doi:10.1007/s00454-002-2817-1

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

P.K. Agarwal
, M. Berg, de
, J. Gudmundsson
, M. Hammar
, H.J. Haverkort

Research output: Contribution to journal › Article › Academic › peer-review

42 Citations (Scopus)

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.

Original language	English
Pages (from-to)	291-312
Journal	Discrete and Computational Geometry
Volume	28
Issue number	3
DOIs	https://doi.org/10.1007/s00454-002-2817-1
Publication status	Published - 2002

Access to Document

10.1007/s00454-002-2817-1

Cite this

@article{05e7bc2546b44fb0b3745ae248dbf536,

title = "Box-trees and R-trees with near-optimal query time",

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 = "P.K. Agarwal and \{Berg, de\}, M. and J. Gudmundsson and M. Hammar and H.J. Haverkort",

year = "2002",

doi = "10.1007/s00454-002-2817-1",

language = "English",

volume = "28",

pages = "291--312",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer",

number = "3",

}

TY - JOUR

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

AU - Agarwal, P.K.

AU - Berg, de, M.

AU - Gudmundsson, J.

AU - Hammar, M.

AU - Haverkort, H.J.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

U2 - 10.1007/s00454-002-2817-1

DO - 10.1007/s00454-002-2817-1

M3 - Article

SN - 0179-5376

VL - 28

SP - 291

EP - 312

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 3

ER -

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

Abstract

Access to Document

Fingerprint

Cite this