Convex Hull

Definition 4.1   Convex hull. In mathematics, the convex hull or convex envelope of a set $S$ of points $\Re^k$ in the Euclidean plane or Euclidean space is the smallest convex set that contains $S$.

The convex hull of a set of points in $\Re^k$ is the most fundamental problem in computational geometry. Given a set of points, all we are interested in computing its convex hull, which is defined to be the smallest convex body containing these points. Of course, the first question one has to answer is how to represent the convex hull. An implicit representation is just to list all the extreme points, where as an explicit representation is to list all the extreme $d$-faces (also called $i-$faces) of dimensions $d=0, 1, ..., k-1$.(see fig. ).

Figure: $d$-faces for $d=2$ (4 $d$-faces for a pyramid).

Note that $d$-faces of dimension 0 are points, dimension $1$ are lines, dimension $2$ are panels of a cuboid, cube, cylinder, pyramid, etc. In figure , the $d-$faces of dimension 2 are the triangle faces: $abd$, $acd$, $bdc$, and $abc$.

Thus the complexity of any convex hull algorithm will have two parts, 1) computation part and output part.

For instance, when $S$ is a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around $S$ (see figure ).

Figure: Convex hull (elastic band analogy).