Accession Number:

ADA413493

Title:

Box-Trees and R-Trees With Near-Optimal Query Time

Descriptive Note:

Conference paper

Corporate Author:

DUKE UNIV DURHAM NC DEPT OF COMPUTER SCIENCE

Report Date:

2001-06-05

Pagination or Media Count:

10.0

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE