Delaunay triangulation: Difference between revisions

Revision as of 14:33, 13 November 2010

Revision as of 21:23, 17 November 2010

Line 1:

[[Image:Delaunay_circumcircles.png|right|thumb|280px|A Delaunay triangulation in the plane with circumcircles shown]]

In [[mathematics]], and [[computational geometry]], a '''Delaunay triangulation''' for a set '''P''' of points in the plane is a [[triangulation (advanced geometry)|triangulation]] DT('''P''') such that no point in '''P''' is inside the [[Circumcircle#Circumcircles_of_triangles|circumcircle]] of any [[triangle (geometry)|triangle]] in DT('''P'''). Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation; they tend to avoid skinny triangles. The triangulation was invented by [[Boris Delaunay]] in 1934<ref name="Delaunay1934">B. Delaunay: ''Sur la sphère vide, Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 7:793&ndash;800, 1934''</ref>.

For a set of points on the same line there is no Delaunay triangulation (in fact, the notion of triangulation is undefined for this case). For four points on the same circle (e.g., the vertices of a rectangle) the Delaunay triangulation is not unique: the two possible triangulations that split the quadrangle into two triangles satisfy the "Delaunay condition", i.e., the requirement that the circumcircles of all triangles have empty interiors.