According to Algorithm 6.8, the Merge operation is
essentially a reverse quadtree decomposition (refer to Figure 6.7).
The graphs are merged three
times, first merging vertically
(the Voronoi graph in the lower left sub-bucket) with
(the Voronoi graph in the upper left sub-bucket), yielding
(the Voronoi graph in the left sub-buckets),
then merging vertically
(the Voronoi graph in the lower right quadrant) with
(the Voronoi graph in the upper right quadrant), yielding
(the Voronoi graph in the right sub-buckets),
and finally merging horizontally
and .
Figure 6.22: Left and right subgraphs before merge
An example of the final horizontal merge step is shown in Figure 6.22 (the left and right subgraph) and Figure 6.23 (the merged resulting graph). The Delaunay graph is drawn with continuous lines, the Voronoi graph is drawn with dashed lines in Figure 6.22 and Figure 6.23.
The Merge method is based on the
assumption that the Delaunay point sets 
of the graphs to
be merged can be separated by a
(vertical or horizontal) straight line (this is always the case for
the quadtree partitioning).
During the merge operation certain edges
and nodes of the left and right subgraph may disappear.
The subgraphs are merged by first constructing a
so-called upper and lower
supporting edge
(
and 
in Figure 6.22).
The supporting edges are found by simultaneously
scanning the convex hulls (which are the
out-most Delaunay polygons) of the left
and right subgraph.
Figure 6.23: Merged left and right subgraphs
A ``zigzag'' open polygon, the so-called dividing chain
(the bold dashed line 
in Figure 6.23) is
constructed starting with the perpendicular bisector of the upper
supporting edge (these are safe Delaunay and Voronoi edges,
respectively, as 
is for sure a part of the
convex hull) and proceeding downwards until a Voronoi edge is cut by
the current ray of .
From the closest intersection the next ray of
is again constructed as
a perpendicular bisector of the new Delaunay edge which connects
the two Delaunay nodes that are now closest to the current ``zigzag'' ray.
This edge insertion, construction of the orthogonal bisecting ray
and intersection with left and right the
Voronoi graphs is repeated until the lower supporting edge is reached.
This merge algorithm is covered in more depth in [95].
The complexity of the overall triangulation algorithm
is 
, also in the classical non-quadtree version, as
a hierarchical decomposition of the point sets (a binary tree with
X-coordinate values as sort key) is used.