\( \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 4.7 - dD Range and Segment Trees
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
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-15b
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


Traits Classes

Search Structure Classes


 Traits Classes
 Search Structures


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