Range tree: Difference between revisions
Appearance
Content deleted Content added
No edit summary |
Unify links to CGAL packages |
||
Line 6: | Line 6: | ||
== External links == |
== External links == |
||
* [http://www.cgal.org/ |
* [http://www.cgal.org/Pkg:RangeSegmentTreesD Range and Segment Trees] in [[CGAL]], the Computational Geometry Algorithms Library. |
||
== References == |
== References == |
Revision as of 07:43, 19 October 2011
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(logd 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, an interval tree stores intervals and allows the intervals containing a given point to be retrieved efficiently.
External links
- Range and Segment Trees in CGAL, the Computational Geometry Algorithms Library.
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.