A set of points is called *convex* if any two points in the set can be connected by a straight line that does not leave the set. For example, all regular polygons have convex interiors, but “bent” shapes or shapes with “holes” in them may not.

The *convex hull* of a set of points is the smallest convex set containing all of the points. In mathematical terms, the convex hull of any set

Intuitively, the points are pegs sticking out of the plane, and the convex hull is the result of shrinking a giant rubber band around that set of points until it is tight.

In a computational context, we’re given a list of

By looking at the convex polygon above, we can quickly see some properties which will be true for *all* convex polygons:

- The leftmost and rightmost points are always part of the convex hull.
- Going anticlockwise, the junction made by three consecutive points is always a left turn.

These two observations are the core of the following algorithm for computing the convex hull:

- Sort the points from left to right.
- Initialise a new list to hold the hull computation.
- Going from left to right, add each point to the list. After adding each point, check that the last three points in the list make a left turn. If they don’t, the remove the second-last point.

This constructs the lower half of the hull. We can construct the upper half of the hull following the same idea, but going from right to left instead of from left to right. Then we join the two halves together (remembering to remove the duplicate end points).

The interactive example below uses the algorithm just described to compute the convex hull of any set of input points. While animating, large dots indicate dots which are part of the convex hull list being built, red indicates a right turn, and green indicates a left turn.

The time complexity analysis for this algorithm is straightforward. Sorting points from left to right takes

- Show that the intersection of any collection of convex sets is convex.
- Show that the union of two convex sets may not be convex.
- Let
V be any vector space over\mathbb{R} , andS = \{v_1, v_2, \ldots, v_n\} be a finite set of vectors fromV . The sum\sum \lambda_i v_i is called a*convex combination*if0 \leq \lambda_i \leq 1 for alli , and\sum \lambda_i = 1 . Show that the set of all convex combinations ofS is equal to the convex hull ofS . - Let
V be a Banach space (a complete normed vector space over\mathbb{R} or\mathbb{C} ), andS \subseteq V be convex. Show that the closure ofS is convex.