## CGAL::Triangulation_hierarchy_3<Tr>

### Definition

The class *Triangulation_hierarchy_3* implements a triangulation augmented
with a data structure which allows fast point location queries. As proved
in [Dev02], this structure has an optimal behavior when it is built
for Delaunay triangulations. It can however be used for other triangulations.

*#include <CGAL/Triangulation_hierarchy_3.h>*

### Parameters

It is templated by a parameter which must be instantiated by one of the CGAL triangulation classes. *In the current implementation, only
**Delaunay_triangulation_3* is supported for *Tr*.

*Tr::Vertex* has to be a model of the concept
*TriangulationHierarchyVertexBase_3*.

*Tr::Geom_traits* has to be a model of the concept
*DelaunayTriangulationTraits_3*.

### Inherits From

*Tr*

*Triangulation_hierarchy_3<Tr>* offers exactly the same functionalities as *Tr*.
Most of them (point location, insertion, removal...) are overloaded to
improve their efficiency by using the hierarchic structure.

Note that, since the algorithms that are provided are randomized, the
running time of constructing a triangulation with a hierarchy may be
improved when shuffling the data points.

However, the I/O operations are not overloaded. So, writing a
hierarchy into a file will lose the hierarchic structure and reading
it from the file will result in an ordinary triangulation whose
efficiency will be the same as *Tr*.

### Implementation

The data structure is a hierarchy
of triangulations. The triangulation at the lowest level is
the original triangulation where operations and point location are to
be performed.
Then at each succedding level, the data structure
stores a triangulation of a small random sample of the vertices
of the triangulation at the preceeding level. Point location
is done through a top-down nearest neighbor query.
The nearest neighbor query is first
performed naively in the top level triangulation.
Then, at each following level, the nearest neighbor at that level
is found through a linear walk performed from
the nearest neighbor found at the preceeding level.
Because the number of vertices in each triangulation is only a small
fraction of the number of vertices of the preceeding triangulation
the data structure remains small and achieves fast point location
queries on real
data.

### See Also

*CGAL::Triangulation_hierarchy_vertex_base_3*

*CGAL::Delaunay_triangulation_3*