# Algorithm for farthest point Voronoi diagram?

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.

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).

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)$$.

• To my understanding there is an nlog n version Nov 7, 2022 at 20:26
• If that's a deal-breaker you should specify it in the question. But if your main interest is an efficient algorithm with a correctness proof, then this might be the best you get. Nov 7, 2022 at 22:17