Editing Delaunay triangulation (section)

== ''d''-dimensional Delaunay ==
For a set {{math|'''P'''}} of points in the ({{mvar|d}}-dimensional) [[Euclidean space]], a '''Delaunay triangulation''' is a [[Triangulation (geometry)|triangulation]] {{math|DT('''P''')}} such that no point in {{math|'''P'''}} is inside the [[circumcircle|circum-hypersphere]] of any {{mvar|d}}-[[simplex]] in {{math|DT('''P''')}}.  It is known{{r|Delaunay1934}} that there exists a unique Delaunay triangulation for {{math|'''P'''}} if {{math|'''P'''}} is a set of points in ''[[general position]]''; that is, the affine hull of {{math|'''P'''}} is {{mvar|d}}-dimensional and no set of {{math|''d'' + 2}} points in {{math|'''P'''}} lie on the boundary of a ball whose interior does not intersect {{math|'''P'''}}.

The problem of finding the Delaunay triangulation of a set of points in {{mvar|d}}-dimensional [[Euclidean space]] can be converted to the problem of finding the [[convex hull]] of a set of points in ({{math|''d'' + 1}})-dimensional space. This may be done by giving each point {{mvar|p}} an extra coordinate equal to {{math|{{abs|''p''}}<sup>2</sup>}}, thus turning it into a hyper-paraboloid (this is termed "lifting"); taking the bottom side of the convex hull (as the top end-cap faces upwards away from the origin, and must be discarded); and mapping back to {{mvar|d}}-dimensional space by deleting the last coordinate. As the convex hull is unique, so is the triangulation, assuming all facets of the convex hull are [[simplex|simplices]]. Nonsimplicial facets only occur when {{math|''d'' + 2}} of the original points lie on the same {{mvar|d}}-[[hypersphere]], i.e., the points are not in general position.{{r|Fukuda}}