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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 05, 2001
Accession Number
ADA413493

Entities

People

  • Herman J. Haverkort
  • Joachim Gudmundsson
  • Mark De Berg
  • Mikael Hammar
  • Pankaj Agarwal

Organizations

  • Duke University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Aspect Ratio
  • Computer Graphics
  • Computer Science
  • Construction
  • Hierarchies
  • Intervals
  • Orientation (Direction)
  • Splitting
  • Trees (Data Structures)
  • Two Dimensional
  • Universities

Fields of Study

  • Computer science

Readers

  • Information Retrieval
  • Military Engineering.
  • Operations Research