TR2002-41

Simple and Efficient Traversal Methods for Quadtrees and Octrees


    •  Frisken, S.; Perry, R., "Simple and Efficient Traversal Methods for Quadtrees and Octrees", Journal of Graphics Tools, Vol. 7, No. 3, May 2003.
      BibTeX Download PDF
      • @article{Frisken2003may,
      • author = {Frisken, S. and Perry, R.},
      • title = {Simple and Efficient Traversal Methods for Quadtrees and Octrees},
      • journal = {Journal of Graphics Tools},
      • year = 2003,
      • volume = 7,
      • number = 3,
      • month = may,
      • url = {http://www.merl.com/publications/TR2002-41}
      • }
  • MERL Contact:
  • Research Areas:

    Algorithms, Computational Geometry, Mechatronics


Quadtrees and octrees are used extensively throughout computer graphics and in many other diverse fields such as computer vision, robotics, and pattern recognition. Managing information stored in quadtrees and octrees requires basic tree traversal operations such as point location, region location, and neighbor searches. This paper presents simple and efficient methods for performing these operations that are inherently non-recursive and reduce the number of comparisons with poor predictive behavior. The methods are table-free, thereby reducing memory accesses, and generalize easily to higher dimensions.