## CGAL::Triangulation_hierarchy_2<Tr>

### Definition

The class *Triangulation_hierarchy_2<Tr>* implements a triangulation augmented with
a data structure which allows fast point location queries.
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 succeeding level, the data structure
stores a triangulation of a small random sample of the vertices
of the triangulation at the preceding 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 preceding level.

Because the number of vertices in each triangulation is only a small
fraction of the number of vertices of the preceding triangulation
the data structure remains small and achieves fast point location
queries on real
data. As proved in [Dev98], this structure has an optimal behavior
when it is built for Delaunay triangulations.
However it can be used as well for other triangulations.
The class *Triangulation_hierarchy_2<Tr>* is templated by a parameter
which is to be instantiated by anyone of the CGAL triangulation
classes.

*#include <CGAL/Triangulation_hierarchy_2.h>*

### Inherits From

*Tr*

### Types

The class *Triangulation_hierarchy_2<Tr>* inherits the types from its base triangulation
class *Tr*.
The class *Triangulation_hierarchy_2<Tr>* offers exactly the same functionalities
as the triangulation Tr does.
Location queries are overloaded to benefit from the
data structure. Modifiers (insertion, removal) are overloaded
to take care of updating the data structure.

Be careful that I/O operations are not overloaded.
Writing a *Triangulation_hierarchy_2<Tr>* into a file
writes only the lowest level triangulation and drop the hierarchy
and reading it from a file results in a triangulation
whose efficiency will be that of an ordinary triangulation.

### See Also

*CGAL::Triangulation_2<Traits,Tds>*

*CGAL::Delaunay_triangulation_2<Traits,Tds>*
*TriangulationHierarchyVertexBase_2*,

*CGAL::Triangulation_hierarchy_vertex_base_2<Vb>*