Delaunay Triangulation

Description

Given a set of points, the Delaunay Triangulation problem is to triangulate the points using the following notion of triangulation.

$AB$ is an edge of the Delaunay triangulation iff there is a circle passing through $A$ and $B$ so that all other points in the point set, $C$, where $C$ is not equal to $A$ or $B$, lie outside the circle. Equivalently, all triangles in the Delaunay triangulation for a set of points will have empty circumscribed circles. That is, no points lie in the interior of any triangle's circumcircle.

Parameters

n: number of points

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Naive algorithm	1934	$O(n^{4})$? (previously $O(n^{2})$)	$O(n)$	Exact	Deterministic
Flipping algorithm	1999	$O(n^{2})$	$O(n)$	Exact	Deterministic	Time
de Berg; Cheong	2008	$O(nlogn)$	$O(n)$	Exact	Deterministic	Time
Bowyer–Watson algorithm	1981	$O(nlogn)$	$O(n)$	Exact	Deterministic	Time
Belloch	2006	$O(nlogn)$	$O(n)$	Exact	Parallel	Time
Guibas; Stofli	1985	$O(nlogn)$	$O(n)$	Exact	Deterministic	Time
Fortune	1992	$O(n^{2})$	$O(n)$	Exact	Deterministic	Time
S-hull (Sinclair)	2010	$O(nlogn)$	$O(n)$	Exact	Deterministic	Time
Dwyer	1987	$O(nlogn)$	$O(n)$?	Exact	Deterministic	Time
Katajainen and M. Koppinen	1987	$O(n log log n)$		Exact	Deterministic	Time
Drysdale; Su	1996	$O(n)$	$O(n)$?	Exact	Deterministic	Time
Dwyer (higher dimensions)	1987	$O(n log log n)$	$O(n)$?	Exact	Deterministic	Time

Time Complexity Graph

Space Complexity Graph

Time-Space Tradeoff