Voronoi Diagrams (Voronoi Diagrams)

From Algorithm Wiki
Revision as of 09:08, 28 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


Given a set of $n$ points in 2-dimensional space, compute the Voronoi diagram with the $n$ points as seeds.


$n$: number of points

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Fortune's algorithm 1986 $O(n \log n)$ $O(n)$ Exact Deterministic Time & Space
Linde–Buzo–Gray algorithm 1980 $O(n \log n)$ Exact Deterministic Time
Bowyer–Watson algorithm 1981 $O(n \log n)$ $O(n)$ Exact Deterministic Time

Time Complexity Graph

Voronoi Diagrams - Time.png