Sökning: onr:"swepub:oai:lup.lub.lu.se:ba31b3ae-6460-4526-a38c-6a3b02026f01" >
Box-trees and R-tre...
Box-trees and R-trees with near-optimal query time
-
Agarwal, PK (författare)
-
de Berg, M (författare)
-
Gudmundsson, J (författare)
-
visa fler...
-
- Hammar, Mikael (författare)
- Lund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science
-
Haverkort, HJ (författare)
-
visa färre...
-
(creator_code:org_t)
- 2002-08-01
- 2002
- Engelska.
-
Ingår i: Discrete & Computational Geometry. - : Springer Science and Business Media LLC. - 0179-5376 .- 1432-0444. ; 28:3, s. 291-312
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://link.springe...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas