# Delaunay Triangulation (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
Fortune 1987 $O(n \log n)$ $O(n)$ Exact Deterministic Time
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(n \log n)$ $O(n)$ Exact Deterministic Time
Bowyer–Watson algorithm 1981 $O(n \log n)$ $O(n)$ Exact Deterministic Time
Belloch 2006 $O(n \log n)$ $O(n)$ Exact Parallel Time
Guibas; Stofli 1985 $O(n \log n)$ $O(n)$ Exact Deterministic Time
Fortune 1992 $O(n^{2})$ $O(n)$ Exact Deterministic Time
S-hull (Sinclair) 2010 $O(n \log n)$ $O(n)$ Exact Deterministic Time
Dwyer 1987 $O(n \log n)$ $O(n)$? Exact Deterministic Time
Katajainen and M. Koppinen 1988 $O(n \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