Voronoi Diagrams: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 2: | Line 2: | ||
== Description == | == Description == | ||
Given a set of n points in 2-dimensional space, compute the Voronoi diagram with the n points as seeds. | Given a set of $n$ points in 2-dimensional space, compute the Voronoi diagram with the $n$ points as seeds. | ||
== Parameters == | == Parameters == | ||
n: number of points | $n$: number of points | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 16: | Line 16: | ||
|- | |- | ||
| [[Fortune's algorithm (Voronoi Diagrams Voronoi Diagrams)|Fortune's algorithm]] || 1986 || $O( | | [[Fortune's algorithm (Voronoi Diagrams Voronoi Diagrams)|Fortune's algorithm]] || 1986 || $O(n \log n)$ || $O(n)$ || Exact || Deterministic || [http://www.wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf Time] & [https://www.wias-berlin.de/people/si/course/files/Fortune87-SweepLine-Voronoi.pdf Space] | ||
|- | |- | ||
| [[Linde–Buzo–Gray algorithm ( Voronoi Diagrams)|Linde–Buzo–Gray algorithm]] || 1980 || $O( | | [[Linde–Buzo–Gray algorithm ( Voronoi Diagrams)|Linde–Buzo–Gray algorithm]] || 1980 || $O(n \log n)$ || || Exact || Deterministic || [https://ieeexplore.ieee.org/document/1094577/ Time] | ||
|- | |- | ||
| [[Bowyer–Watson algorithm (Voronoi Diagrams Voronoi Diagrams)|Bowyer–Watson algorithm]] || 1981 || $O( | | [[Bowyer–Watson algorithm (Voronoi Diagrams Voronoi Diagrams)|Bowyer–Watson algorithm]] || 1981 || $O(n \log n)$ || $O(n)$ || Exact || Deterministic || [https://academic.oup.com/comjnl/article/24/2/167/338200 Time] | ||
|- | |- | ||
|} | |} | ||
| Line 27: | Line 27: | ||
[[File:Voronoi Diagrams - Time.png|1000px]] | [[File:Voronoi Diagrams - Time.png|1000px]] | ||
Latest revision as of 10:08, 28 April 2023
Description
Given a set of $n$ points in 2-dimensional space, compute the Voronoi diagram with the $n$ points as seeds.
Parameters
$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
