Algorithm for farthest point Voronoi diagram?

Question

I am looking for an algorithm to compute the furthest point Voronoi diagram and I don't seem to be able to find anything decent. The most complete one I have found are these slides and this terribly written wordpress site with a cool tool:

But I am not finding any well written text explaining and proving an algorithm to get the voronoi diagram, keyword being proving.

Answer 1

There are linear-time algorithms to construct a farthest-point Voronoi diagram given a sorted list of vertices of a convex polygon. For a general set of points, first computing the convex hull results in $O(n \log n)$-time algorithms.

First algorithm [1] is deterministic. Second algorithm [2] is randomized but much simpler than the first algorithm.

• [1] Aggarwal, Alok, et al. "A linear-time algorithm for computing the Voronoi diagram of a convex polygon." Discrete & Computational Geometry 4.6 (1989): 591-604.
• [2] Chew, L. Paul. "Building Voronoi diagrams for convex polygons in linear expected time." (1990).

Answer 2

It's published in Journal of Computational Geometry: Theory and Applications, DOI 10.1016/j.comgeo.2010.11.004 by Cheong, Otfried and Everett, Hazel and Glisse, Marc and Gudmundsson, Joachim and Hornus, Samuel and Lazard, Sylvain and Lee, Mira and Na, Hyeon-Suk.

The result you are looking for is:

Theorem 11. The farthest-polygon Voronoi diagram $\mathfrak{F}( \cal S )$ of a family $\cal S$ of disjoint polygonal sites of total complexity $n$ can be computed in time $O(n \log^3 n)$.