dD Range and Segment Trees Reference

Gabriele Neyer

Range and segment trees allow to perform window queries on point sets, and to enumerate all ranges enclosing a query point. The provided data structures are static and they are optimized for fast queries.

Introduced in: CGAL 0.9
BibTeX: cgal:n-rstd-22b
License: GPL

This chapter presents the CGAL range tree and segment tree data structures.

The range tree is theoretically superior to the \( Kd\)-tree, but the latter often seems to perform better. However, the range tree as implemented in CGAL is more flexible than the \( Kd\)-tree implementation, in that it enables to layer together range trees and segment trees in the same data structure.

Classified Reference Pages

Concepts

• RangeSegmentTreeTraits_k
• Sublayer

Traits Classes

• CGAL::Range_segment_tree_set_traits_2<R>
• CGAL::Range_segment_tree_set_traits_3<R>
• CGAL::Range_tree_map_traits_2<R,T>
• CGAL::Range_tree_map_traits_3<R,T>
• CGAL::Segment_tree_map_traits_2<R,T>
• CGAL::Segment_tree_map_traits_3<R,T>
• CGAL::tree_interval_traits
• CGAL::tree_point_traits

Search Structure Classes

• CGAL::Range_tree_d<Data, Window, Traits>
• CGAL::Range_tree_k<Traits>
• CGAL::Segment_tree_d<Data, Window, Traits>
• CGAL::Segment_tree_k<Traits>
• CGAL::Tree_anchor<Data, Window>

Modules
	Concepts
	Traits Classes
	Search Structures

Classes
class	CGAL::Tree_anchor< Data, Window >
	Tree_anchor is also derived from Tree_base. More...