Delaunay Triangulation (Delaunay Triangulation)
Revision as of 10:22, 15 February 2023 by Admin (talk | contribs) (Created page with "{{DISPLAYTITLE: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 triangu...")
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