# Chapter 62
Spatial Searching

Hans Tangelder and Andreas Fabri
This package provides data structures and algorithms for exact and approximate distance browsing, supporting

- both nearest and furthest neighbor searching,
- both exact and approximate searching,
- (approximate) range searching,
- (approximate) k-nearest and k-furthest neighbor searching,
- (approximate) incremental nearest and incremental furthest neighbor searching,
- query items representing points and spatial objects.

The spatial searching package consists of the following concepts and classes that are described in the reference pages.

### Search Classes

CGAL::K_neighbor_search<Traits, GeneralDistance, Splitter, SpatialTree>
CGAL::Incremental_neighbor_search<Traits, GeneralDistance, Splitter, SpatialTree>
CGAL::Orthogonal_incremental_neighbor_search<Traits, OrthogonalDistance, Splitter, SpatialTree>
CGAL::Orthogonal_k_neighbor_search<Traits, OrthogonalDistance, Splitter, SpatialTree>
CGAL::Kd_tree<Traits, Splitter, UseExtendedNode>

### Range Query Item Classes

CGAL::Fuzzy_iso_box<Traits>
CGAL::Fuzzy_sphere<Traits>

### Search Traits Classes

CGAL::Search_traits_2<Kernel>
CGAL::Search_traits_3<Kernel>
CGAL::Search_traits_d<Kernel>
CGAL::Search_traits<NT,Point,CartesianIterator,ConstructCartesianIterator,ConstructMinVertex,ConstructMaxVertex>

### Distance Classes

CGAL::Euclidean_distance<Traits>
CGAL::Euclidean_distance_sphere_point<Traits>
CGAL::Manhattan_distance_iso_box_point<Traits>
CGAL::Weighted_Minkowski_distance<Traits>

### Splitter Classes

CGAL::Sliding_midpoint<Traits, SpatialSeparator>
CGAL::Sliding_fair<Traits, SpatialSeparator>
CGAL::Fair<Traits, SpatialSeparator>
CGAL::Median_of_max_spread<Traits, SpatialSeparator>
CGAL::Median_of_rectangle<Traits, SpatialSeparator>
CGAL::Midpoint_of_max_spread<Traits, SpatialSeparator>
CGAL::Midpoint_of_rectangle<Traits, SpatialSeparator>

### Advanced Classes

CGAL::Kd_tree_node<Traits, Splitter, UseExtendedNode>
CGAL::Kd_tree_rectangle<Traits>
CGAL::Plane_separator<FT>

### Concepts

FuzzyQueryItem
GeneralDistance
OrthogonalDistance
SearchTraits
SpatialSeparator
SpatialTree

### Alphabetical Listing of Reference Pages

- Euclidean_distance<Traits>

- Euclidean_distance_sphere_point<Traits>

- Fair<Traits, SpatialSeparator>

- FuzzyQueryItem

- Fuzzy_iso_box<Traits>

- Fuzzy_sphere<Traits>

- GeneralDistance

- Incremental_neighbor_search<Traits, GeneralDistance, Splitter, SpatialTree>

- K_neighbor_search<Traits, GeneralDistance, Splitter, SpatialTree>

- Kd_tree<Traits, Splitter, UseExtendedNode>

- Kd_tree_node<Traits, Splitter, UseExtendedNode>

- Kd_tree_rectangle<Traits>

- Manhattan_distance_iso_box_point<Traits>

- Median_of_max_spread<Traits, SpatialSeparator>

- Median_of_rectangle<Traits, SpatialSeparator>

- Midpoint_of_max_spread<Traits, SpatialSeparator>

- Midpoint_of_rectangle<Traits, SpatialSeparator>

- OrthogonalDistance

- Orthogonal_incremental_neighbor_search<Traits, OrthogonalDistance, Splitter, SpatialTree>

- Orthogonal_k_neighbor_search<Traits, OrthogonalDistance, Splitter, SpatialTree>

- Plane_separator<FT>

- SearchTraits

- Search_traits_2<Kernel>

- Search_traits_3<Kernel>

- Search_traits_d<Kernel>

- Search_traits<NT,Point,CartesianIterator,ConstructCartesianIterator,ConstructMinVertex,ConstructMaxVertex>

- Sliding_fair<Traits, SpatialSeparator>

- Sliding_midpoint<Traits, SpatialSeparator>

- SpatialSeparator

- SpatialTree

- Splitter

- Weighted_Minkowski_distance<Traits>