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
Katajainen and M. Koppinen	1987	$O(n log log n)$		Exact	Deterministic	Time

Time Complexity graph

Error creating thumbnail: Unable to save thumbnail to destination

Space Complexity graph

Error creating thumbnail: Unable to save thumbnail to destination

Pareto Decades graph

Error creating thumbnail: Unable to save thumbnail to destination