With the two aforementioned improvements the very basic algorithm of the quadtree-based divide-and-conquer Voronoi tessellation is as follows.
The resulting graphs for the four trivial cases
are depicted in Figure 6.21. The Delaunay graphs
are drawn with continuous lines and the Voronoi graphs are dotted.
Note that choosing a bucket capacity of three Delaunay nodes simplifies
the implementation of the Divide step (the decomposition of
into subsets) as it can solely rely on the
already existing quadtree partitioning.
Figure 6.21: Voronoi and Delaunay graphs for the trivial cases of
0, 1, 2, and 3 grid points
Although these are trivial cases the consistent treatment is not entirely trivial and the importance and impact of a proper implementation of these cases (although often left out of consideration in classical texts) should not be disregarded, as it has a considerable impact on the applicable assumptions and demanded prerequisites of all other parts of the algorithm. What, e.g., is the convex hull of two points or of a single point and how should two single points be merged? It is fairly obvious that two points are merged by one Delaunay and one Voronoi edge (resulting in a graph similar to the trivial case for 2 grid points, Figure 6.21), but a consistent implementation of all these special cases spoils the simplicity of the original algorithm.
The actual ``tessellation work'' is of course done in the Merge step. Here, all the degeneracies must be detected and handled. An exceedingly detailed description of the merge algorithm is not appropriate here as it contains no essentially new or interesting aspects, but the basic scheme is as follows.
