delaunayn

Delaunayn is a term commonly used to refer to the Delaunay triangulation in n-dimensional space, and it is also the name of a MATLAB function that computes this triangulation for a set of points in any dimension. In MATLAB, delaunayn(X) returns a list of simplices (for example, triangles in 2D, tetrahedra in 3D, and higher-dimensional analogues) by providing indices into the input point matrix X.

The Delaunay triangulation is a tessellation of a point set with the property that the circumsphere (or circumscribed circle in two dimensions) of every simplex contains no other input points in its interior. This empty circumsphere property makes the Delaunay triangulation the geometric dual of the Voronoi diagram. The construction generalizes naturally to higher dimensions, where simplices replace triangles and tetrahedra replace triangles in three dimensions.

Delaunay triangulations are widely used in mesh generation, numerical interpolation, computer graphics, and geographic information systems. They can be produced by several algorithmic approaches, including incremental insertion, divide-and-conquer, and flipping methods, with practical runtimes that are near O(n log n) in fixed dimensions, though worst-case complexity can be higher.

Robustness considerations are important in practice; degenerate configurations (such as cocircular or cocircularly aligned points) can lead to non-unique triangulations, in which case implementations apply tie-breaking or perturbation. In software libraries, delaunayn is a standard entry point for computing n-dimensional Delaunay triangulations, while the broader concept is known as Delaunay triangulation, with connections to related structures like the Voronoi diagram. The concept is named after Boris Delaunay, a mathematician who contributed to its development.