Range tree

In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be efficiently retrieved, and is typically used in two or higher dimensions.

It is similar to a kd-tree except with faster query times of O(log^d n + k) but worse storage of O(n log^(d-1) n), with d being the dimension of the space, n being the number of points in the tree, and k being the number of points retrieved for a given query.

Range trees may be contrasted with interval trees: instead of storing points and allowing points in a given range to be retrieved efficiently, it stores intervals and allows the intervals containing a given point to be retrieved efficiently.

External links

• A C# Implementation of a Range Tree
• CGAL : Computational Geometry Algorithms Library in C++ contains a robust implementation of Range Trees

References

• Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry, Second Revised Edition. Springer-Verlag 2000. Section 5.3: Range Trees, pp.105-110.
• David M. Mount. Lecture Notes: CMSC 754 Computational Geometry. Lecture 23: Orthogonal Range Trees, pp. 102-104.