\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 5.0 - dD Range and Segment Trees
dD Range and Segment Trees Reference

segment_tree.png
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-19b
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

Traits Classes

Search Structure Classes

Modules

 Concepts
 
 Traits Classes
 
 Search Structures
 

Classes

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