3
$\begingroup$

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.

$\endgroup$

2 Answers 2

4
+25
$\begingroup$

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).
$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ To my understanding there is an nlog n version $\endgroup$
    – Makogan
    Nov 7, 2022 at 20:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – Pål GD
    Nov 7, 2022 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.