Fortune's algorithm is a sweep line algorithm for generating a Voronoi diagram from a set of points in a plane using O(n log n) time and O(n) space.[1][2] It was originally published by Steven Fortune in 1986 in his paper "A sweepline algorithm for Voronoi diagrams."[3]
- ^ de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0 Section 7.2: Computing the Voronoi Diagram: pp.151–160.
- ^ Austin, David, Voronoi Diagrams and a Day at the Beach, Feature Column, American Mathematical Society.
- ^ Steven Fortune. A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry. Yorktown Heights, New York, United States, pp.313–322. 1986. ISBN 0-89791-194-6. ACM Digital LibrarySpringerLink