A Note on Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams

We note that a few modifications to the Guibas and Stolfi's algorithm for Nearest-Neighbor Delaunay Triangulation produce an algorithm for the Farthest-Neighbor Delaunay Triangulation (a triangulation of the convex hull of the set of points) that, like the original, runs in optimal $O(n \log n)$ time and linear space.

1992