Page "Delaunay triangulation" Paragraph 38

A divide and conquer algorithm for triangulations in two dimensions is due to Lee and Schachter which was improved by Guibas and Stolfi and later by Dwyer.

In this algorithm, one recursively draws a line to split the vertices into two sets.

The Delaunay triangulation is computed for each set, and then the two sets are merged along the splitting line.

Using some clever tricks, the merge operation can be done in time O ( n ), so the total running time is O ( n log n ).