# Voronoi Diagrams (Voronoi Diagrams)

Jump to navigation
Jump to search

## 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 |