An excellent introduction to quadtrees is given in [119]. What first comes to mind for the sole point location problem is a (balanced) point quadtree. The classical point quadtree method has, however, some severe disadvantages when point coordinates are allowed to change (e.g. during grid relaxation steps) or when many insertions and deletions take place (e.g. during boundary refinement).
It turned out that a bucket point region quadtree [pp.85]sam90 is superior to other approaches for several reasons. It is very easy to implement and the theoretically less efficient point location is by far outweighed by the ``implicit balancing'' of the method. (The sequence of point insertion has no impact on the final tree structure without the need to explicitly balance the tree.) It is insensitive to coordinate changes and very efficient for point deletion and range inquiries which makes it ideally suited for applications that require a broad spectrum of fast operations on a rather limited but dynamical data set.
Figure 6.7: Subdivision scheme of a region quadtree
Figure 6.7 shows the basic subdivision scheme of a region quadtree. Each region is divided recursively into its four quadrants, forming four subregions. The quadrants are indexed as in Figure 6.7.
Figure 6.8: Geometrical view of a bucket point
region quadtree used
for the location of Delaunay grid points.
Figure 6.8 shows the graphical representation of a simple example of such a bucket point region quadtree for a test structure that contains only geometry points. The bucket capacity (the maximum number of points allowed in a leaf bucket) chosen is 3, which matches the ``merge threshold'' (the maximum number of points for trivial cases) of the triangulation algorithm (see Section 6.5).
Figure 6.9: Data structure of a region quadtree used
for the location of Delaunay grid points.
The quadtree is adaptively refined during the iterative insertion of
grid and geometry points.
Figure 6.9 shows the final data structure of the quadtree shown in
Figure 6.8. The bucket capacity is three and the
maximum depth of the quadtree is four. Every bucket either consists of
four sub-buckets or is a leaf bucket. To illustrate the adaptive
construction of the quadtree, suppose the points 
to 
have
already been inserted (see Figure 6.10) and point 
is to be
entered into the quadtree. The location of reveals that it must be
put into a bucket which is already entirely occupied (by , 
, and
). Hence this bucket must be refined (split into four sub-buckets),
as shown in Figure 6.11.
Figure 6.10: The insertion of point exceeds the level 1
bucket capacity.
Figure 6.11: After the first refinement, the
insertion of point exceeds the level 2 bucket capacity.
After the first refinement
(Figure 6.11), , , and still
occupy the bucket where is to be put into, so a second refinement
has to be performed which finally separates the occupants into
different buckets and creates a vacancy for .
Figure 6.12: Successful insertion of into a level 3
bucket without further refinement.
The complexity of insertion, location, and
deletion operations depends on the
maximum depth
of the tree which is
in turn a function of the minimum Euclidean distance separating two
points and of the coordinate range of the region that is covered by the root
bucket. The worst case complexity for deletion and insertion is 
and the worst case complexity for range search operations is
, where 
is the depth of the tree and 
is the number
of points found. In virtually all realistic cases, the depth
of the tree is 
for 
grid points.