Delaunay Triangulation (Delaunay Triangulation)
Jump to navigation
Jump to search
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
Space Complexity graph
Pareto Decades graph
