Convex Hull and Delaunay Triangulation

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 P_j. In the graph theory sense, the Voronoi diagram is the dual graph of the Delaunay triangulation.