5.3.1 Divide-and-Conquer

The point set $P$ is recursively divided into halves until the subsets contain a minimum number of points. These smallest sets of two or three points can be linked yielding edges or triangles. The following conquer step merges the subsets. Thereby the convex hull of a subset is traversed and linked to the other subset. Re-connecting the points by e.g. flip operations to satisfy the Delaunay criterion is equivalent to finding the dividing polygonal chain between the Voronoi diagrams of the two subsets. The dividing chain which consists of Voronoi edges can be constructed in linear time which results in an overall $O(n\log n)$ performance [123].