Machine Learning & Data Science Vector Search Delauny Graphs
The Delaunay triangulation is the dual graph of the Voronoi diagram.
- Connect two sites with an edge if their Voronoi cells share a boundary.
- In 2D, this produces a triangulation (a set of non-overlapping triangles) covering the convex hull of the points.
Mesh generation, interpolation (esp. natural neighbour interpolation), computer graphics, finite element methods.
- Maximises the minimum angle of all the angles in the triangulation (avoids skinny triangles).
- Equivalent to saying: for each triangle in the triangulation, the circumcircle of that triangle contains no other points from the set inside it.
- In higher dimensions, it generalises to simplices (tetrahedra, etc.).
