Convex hull

The convex hull for a geometrical object or a set of geometrical objects is the minimal convex set containing given objects.

For planar objects, i.e., lying in the plane, an easy way to visualize the convex hull is to imagine a rubber band tightly stretched to encompass given objects; when released, it will assume the shape of the required convex hull.

In computational geometry, a number of different algorithms exist for computing the convex hull of a set of points (usually in the plane). The simplest (although not the most time efficient) of these, the so-called gift wrapping algorithm, has O(NK) complexity, where N is the number of points and K is the number of points on the convex hull. The gift wrapping algorithm begins with a point A known to be on the convex hull (such as the leftmost point) and selects the point B such that all points are to the left (or right) of the line AB. Repeating with B and so on until one reaches A again yields the convex hull. The gift wrapping algorithm is exactly analogous to the process of winding a string (or wrapping paper) around the set of points.