Delaunay triangulation is an
algorithm
for generating a
mesh of
triangles out of an
irregular set of
points.
The algorithm
minimizes the
maximum
angle over all possible triangulations
(thus avoiding "
skinny" triangles).
It is based on the following "rule";
Given a finite set of points in a plane,
three points contribute to a triangle
if the circumcircle - a circle whose
circumference goes through the points -
contains no other point in its interior.
Given an appropriate handling of
degeneracies, e.g.
4 or more co-circular
points, this will produce a unique
triangulation.