dD Search Structures

This chapter presents the CGAL range tree, segment tree, and $$Kd-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.

Concepts

KdtreeDTraits
RangeSegmentTreeTraits_k
Sublayer

Traits Classes

CGAL::Kdtree_Interface<Point>
CGAL::Kdtree_Interface_2d<Point>
CGAL::Kdtree_Interface_3d<Point>
CGAL::Range_segment_tree_traits_set_2<R>
CGAL::Range_segment_tree_traits_set_3<R>
CGAL::Range_tree_traits_map_2<R,T>
CGAL::Range_tree_traits_map_3<R,T>
CGAL::Segment_tree_traits_map_2<R,T>
CGAL::Segment_tree_traits_map_3<R,T>
CGAL::tree_interval_traits
CGAL::tree_point_traits

Search Structure Classes

CGAL::Kdtree_d<Traits>
CGAL::Kdtree_d<Traits>::Box
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>

Alphabetical Listing of Reference Pages

• Kdtree_d<Traits>.

• Kdtree_d<Traits>::Box.

• KdtreeDTraits.

• Kdtree_Interface<Point>.

• Kdtree_Interface_2d<Point>.

• Kdtree_Interface_3d<Point>.

• RangeSegmentTreeTraits_k.

• Range_segment_tree_traits_set_2<R>.

• Range_segment_tree_traits_set_3<R>.

• Range_tree_d<Data, Window, Traits>.

• Range_tree_k<Traits>.

• Range_tree_traits_map_2<R,T>.

• Range_tree_traits_map_3<R,T>.

• Segment_tree_d<Data, Window, Traits>.

• Segment_tree_k<Traits>.

• Segment_tree_traits_map_2<R,T>.

• Segment_tree_traits_map_3<R,T>.

• Sublayer.

• tree_interval_traits.

• tree_point_traits.

• Tree_anchor<Data, Window>.