Fortune's algorithm
Voronoi diagram generation algorithm / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Fortune's algorithm?
Summarize this article for a 10 year old
SHOW ALL QUESTIONS
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]
![Fortune's Algorithm Animation](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0c/Fortunes-algorithm-slowed.gif/220px-Fortunes-algorithm-slowed.gif)