The convex hull of a given set
is the smallest convex set that contains
. If
is finite, that is, if
, where the
are points, then the convex hull is always a polygon whose vertices are a subset of
.
The Delaunay triangulation of a given set of points
is a triangulation of the convex hull of
such that no point of
is inside the circumcircle of any triangle of
.
The Voronoi diagram of the set of points
is the plane partition containing the regions
of points whose distance from
is no greater than the distance from any other point
Pj. In the graph theory sense, the Voronoi diagram is the dual graph of the Delaunay triangulation.
