Convex Hull and Delaunay Triangulation
For three or more points, you can see the convex hull (blue), the Delaunay triangulation (red), or the Voronoi diagram (green).
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 . In the graph theory sense, the Voronoi diagram is the dual graph of the Delaunay triangulation.