# Is Fortune's algorithms for Voronoi diagrams described anywhere by Prof. Fortune?

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.

– D.W.
Jan 7 at 20:44
• @D.W. thanks for the suggestion, I'll do that. Jan 9 at 11:33

• @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. Jan 7 at 15:10