We provide an alternative to the class Apollonius_graph_2<Gt,Agds> for the dynamic construction of the Apollonius graph. The Apollonius_graph_hierarchy_2<Gt,Agds> class maintains a hierarchy of Apollonius graphs. The bottommost level of the hierarchy contains the full Apollonius diagram. A site that is in level $$i, is in level $$i+1 with probability $$1/ where $$> 1 is some constant. The difference between the Apollonius_graph_2<Gt,Agds> class and the Apollonius_graph_hierarchy_2<Gt,Agds> is on how the nearest neighbor location is done. Given a point $$p the location is done as follows: at the top most level we find the nearest neighbor of $$p as in the Apollonius_graph_2<Gt,Agds> class. At every subsequent level $$i we use the nearest neighbor found at level $$i+1 to find the nearest neighbor at level $$i. This is a variant of the corresponding hierarchy for points found in [Dev98]. The class has two template parameters which have essentially the same meaning as in the Apollonius_graph_2<Gt,Agds> class. The first template parameter must be a model of the ApolloniusGraphTraits_2 concept. The second template parameter must be a model of the ApolloniusGraphDataStructure_2 concept. However, the vertex base class that is to be used in the Apollonius graph data structure must be a model of the ApolloniusGraphHierarchyVertexBase_2 concept. The second template parameter defaults to Triangulation_data_structure_2< Apollonius_graph_hierarchy_vertex_base_2< Apollonius_graph_vertex_base_2<Gt,true> >, Triangulation_face_base_2<Gt> >.
The Apollonius_graph_hierarchy_2<Gt,Agds> class derives publicly from the Apollonius_graph_2<Gt,Agds> class. The interface is the same with its base class. In the sequel only the methods overridden are documented.
#include <CGAL/Apollonius_graph_hierarchy_2.h>
 
Creates an hierarchy of Apollonius graphs using gt as
geometric traits.
 
 
 
Creates an Apollonius graph hierarchy using
gt as geometric traits and inserts all sites in the
range [first, beyond).
 
 
Copy constructor. All faces, vertices and interlevel pointers
are duplicated. After the construction, agh and other refer
to two different Apollonius graph hierarchies: if
other is modified, agh is not.

 
 Assignment. All faces, vertices and interlevel pointers are duplicated. After the construction, agh and other refer to two different Apollonius graph hierarchies: if other is modified, agh is not. 
 

 
Inserts the sites in the range
[first,beyond). The number of sites in the range
[first, beyond) is returned. Precondition: Input_iterator must be a model of InputIterator and its value type must be Site_2.  

 
Inserts the site s in the Apollonius graph hierarchy. If s is visible then the vertex handle of s is returned, otherwise Vertex_handle(NULL) is returned.  

 
Inserts s in the Apollonius graph hierarchy using the site associated with vnear as an estimate for the nearest neighbor of the center of s. If s is visible then the vertex handle of s is returned, otherwise Vertex_handle(NULL) is returned. A call to this method is equivalent to agh.insert(s); and it has been added for the sake of conformity with the interface of the Apollonius_graph_2<Gt,Agds> class. 

 
Finds the nearest neighbor of the point p. In other words it finds the site whose Apollonius cell contains p. Ties are broken arbitrarily and one of the nearest neighbors of p is returned. If there are no visible sites in the Apollonius diagram Vertex_handle(NULL) is returned.  

 
Finds the nearest neighbor of the point p. If there are no visible sites in the Apollonius diagram Vertex_handle(NULL) is returned. A call to this method is equivalent to agh.nearest_neighbor(p); and it has been added for the sake of conformity with the interface of the Apollonius_graph_2<Gt,Agds> class. 