Farthest Voronoi Diagram

Recently I've been looking at the problem Euclid. Basically, it requires computing the regions of the farthest-point Voronoi diagram in $$$O(n \log n)$$$ or better.

We know that the nearest can be computed with D&C, Fortune's Algorithm, Delaunay Triangulation, 3D Convex Hull (as mentioned by Monogon in his Efficient 3D Convex Hull Tutorial).

After doing some research, I found The farthest point Delaunay triangulation minimizes angles, in which David Eppstein notes that 'It is a curious fact that both the nearest and farthest point Voronoi diagrams can be obtained as the planar projections of the lower and upper portions of the convex hull of the transformed point set'.

So, that's it. However, I want to detail the process in case it helps anyone, and also highlight a few details that I think are useful.

Nearest and Farthest Voronoi Diagram

Transform every point $$$(x, y) \to (x, y, x^2 + y^2)$$$.
Compute the 3D Convex Hull.
Filter the faces: examine the $$$z$$$-component of the normal vector for each face. Keep faces where this component is $$$ \gt 0$$$ for the farthest-point diagram, or $$$ \lt 0$$$ for the nearest-point diagram.
Store the neighbors of every point.
Compute each region by applying half-plane intersection exclusively to its neighbors.

Half-plane Intersection

Alternatively, both diagrams can be obtained in $$$O(n^2 \log n)$$$ time using half-plane intersection. For point $$$P[i]$$$, we store the half-plane $$$[(P[i] + P[j]) / 2, \text{orthogonal}(P[j] - P[i])]$$$ for the nearest-point diagram, and $$$[(P[i] + P[j]) / 2, \text{orthogonal}(P[i] - P[j])]$$$ for the farthest-point diagram.

Another interesting property is that only the points on the convex hull have a farthest-point Voronoi cell.

Second Order

Following a similar idea, we can obtain the Second-Order Voronoi Diagram (nearest) within the same time complexity. Since the Delaunay Triangulation has a linear number of triangles, we can take the cell of the point $$$p_i$$$, remove $$$p_i$$$, and recompute the Voronoi diagram using only its neighbors. This allows us to find the second-order cells with practically the same complexity.

This can be applied incrementally to obtain higher orders, but achieving the $$$O(k^2 n \log n)$$$ time complexity, as mentioned by Der-Tsai Lee in On k-Nearest Neighbor Voronoi Diagrams in the Plane, requires a more sophisticated implementation and further geometric observations.

Circular Inversion

If we take a point $$$p_i$$$ and invert all other points around it, the convex hull of the resulting set gives us its neighbors. Furthermore, if $$$p_i$$$ lies on the convex hull of the original set, we can apply the same inversion; excluding $$$p_i$$$ from the new hull computation, the points that remain "visible" from $$$p_i$$$'s position will correspond to its neighbors in the farthest-point diagram.