2
$\begingroup$

One popular algorithm to find the Voronoi diagram out of a collection of points (sites) in the plane is Fortune's algorithm. It is usually described in terms of a sweep line, whose interaction with sites give raise to parabolas, whose intersections eventually provide the Voronoi diagram.

The Wikipedia page also includes a reference to Fortune's paper about the algorithm. (The paper is provided online by some universities, but I'm not sure about the copyright status of those copies so I will not link them here.)

Last, there is also an implementation of the algorithm described in the paper, made in C by Prof. Fortune. One page linking to the original is kept at the Internet Archive.

From what I saw (e.g. here from some years ago), the implementation is consistent with the paper, but both are very different from the popular description found around. As an example, the paper talks about hyperbolas, while the popular description deals with parabolas.

Hence the question: where can I find the original description by Prof. Fortune of what is widely regarded as Fortune's algorithm for Voronoi diagrams (the one with parabolas)?

UPDATE The accepted answer below makes the following citation:

[1]: L. J. Guibas and J. Stolfi. Ruler, compass and computer: The design and analysis of geometric algorithms. In R. A. Earnshaw, editor, Theoretical Foundations of Computer Graphics and CAD. NATO ASI Series F, vol. 40, pages 111–165. Springer-Verlag, 1988.

Prof. L. J. Guibas published some online material in CS268 Geometric Algorithms, available in the Lecture Notes page, including a PDF copy of a derived paper.

Improve this question
$\endgroup$
2
  • $\begingroup$ Please don't edit your question to include the answer into the question. Instead, write an answer of your own if you have something new to contribute over others' answers, or do nothing if everything has already been covered in the answer below. Our site works a bit differently from others you might be used to: we are Q&A site with strict quality standards, and we want answers to appear in the 'Your Answer' box, not in the question. $\endgroup$
    – D.W. ♦
    Jan 7 at 20:44
  • $\begingroup$ @D.W. thanks for the suggestion, I'll do that. $\endgroup$
    – polettix
    Jan 9 at 11:33

1 Answer 1

Reset to default
1
$\begingroup$

The "popular description" of Fortune's algorithm in terms of parabolas does not appear to be due to Fortune, but due to Guibas and Stolfi [1]. They start by analyzing the geometrical interpretation of Fortune's algorithm in section 5 of the original paper, and then deviate from the original paper by keeping track of the parabola front instead of working with the transformed Voronoi diagram.

So, to answer your question, given that the parabola interpretation in [1] only cites Fortune's paper, I believe the interpretation is original to Guibas and Stolfi. Therefore, the original description of the interpretation "with parabolas" is in [1], and such a description authored by Fortune does not exist. (or would not be original)

[1]: L. J. Guibas and J. Stolfi. Ruler, compass and computer: The design and analysis of geometric algorithms. In R. A. Earnshaw, editor, Theoretical Foundations of Computer Graphics and CAD. NATO ASI Series F, vol. 40, pages 111–165. Springer-Verlag, 1988.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you very much. The paper [1] does not seem to indicate how the hyperbolas-based description by Fortune is related to the parabolas-based they devised, so it indeed seems like they started from the idea that a sweep-line algorithm was indeed possible and maybe found a different, more approachable way to build one. Thanks! $\endgroup$
    – polettix
    Jan 7 at 14:22
  • 1
    $\begingroup$ @polettix Well, I'd say the two sweep-line algorithms are a bit more strongly related than that: Fortune notes in section 5 that translating the plane $P_c$ in 3D gives the sequence of Voronoi edges constructed by his algorithm. Guibas and Stolfi use this observation to obtain the same sequence in a different way, by noting that the intersection of this plane and one of the cones is a parabola (and remains a parabola after projection into the original plane). In other words, you could say both algorithms implement a sweep of the plane $P_c$ along the "Voronoi cones" in 3D. $\endgroup$
    – Discrete lizard ♦
    Jan 7 at 15:10
  • $\begingroup$ A version of the document [1] is made available by one of the authors as lecture notes here: graphics.stanford.edu/courses/cs268-09-winter/notes/… $\endgroup$
    – polettix
    Jan 9 at 11:34

Your Answer

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

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