Combining the refinement criterion with the grid point insertion
in a loop over all boundary elements yields the
refinement algorithm.
The refinement of an edge creates two new edges and one additional
boundary grid point. These changes are immediately applied to the
global graph data which in turn affect the loops that are performed
over all edges and over all nodes in the vicinity of the current edge.
Due to proper functional interfaces this does not pose an
implementation problem, but a global variable 
is needed
to indicate whether a refinement took place during the last scan of
all edges and the algorithm terminates when the final scan of all
edges did not reveal an edge to be refined.
This algorithm is simplified and reflects only the basic flow of the real implementation.
Figure 6.20: The interface edge 
and its selected
quadtree buckets.
To determine all nodes in vicinity of the boundary edge 
efficiently, the
quadtree structure can be utilized as shown in Figure 6.20.
A selection quadrangle is constructed for the edge which contains
the circle 
. This selection quadrangle (dashed lines in
Figure 6.20) intersects only the shaded buckets and hence only
the points 
are subject to further investigation.
One can easily argue that this bucket selection method will cause
the refinement algorithm to show an overall average
complexity 
, where 
is the number of
boundary edges (after refinement) and 
is the number of points
(also after refinement).
Examples and applications of the boundary refinement algorithm can be
found in Section 6.7.