The Convex Hull of a set of points in the plane is the shape you would get if you stretched an elastic band around the points, and let it snap tight. A more formal mathematical definition is as follows.
A set C is convex if for any x and y in C, and for any l between 0 and 1, the point lx+(1-l)y is also in C. That is, if x and y are in C, the line segment between x and y is completely contained in C. So for example, circles, squares and ovals are convex, but crosses or crescent moons are not. The convex hull of a set of points is the ßmallest possible" convex hull containing the points. More technically, it is the intersection of all convex sets containing the points.
An alternative definition, at least if the set of points P = {p1,p2,...,pn} is finite, is that the convex hull consists of all points x which may be written x = l1 p1 + l2 p2 + ... + ln pn, for some l1,l2,...,ln such that l1+l+2+...+ln = 1.
The DotPlacer Applet (on this site) allows you to place a set of points on the screen, and have it draw the convex hull for you (and many other things). You can even move the points around, and watch the shape change. Try it!
I used the following algorithm to draw the Convex hull. First of all, I found the point p1 with the smallest x coordinate. Then, I chose a vector v1 pointing up the y axis. Then I found the point p2 for which the line p1p2 made the smallest angle with v1, and let v2 be a vector in the direction of this line. Then, I used p2 and v2 to find p3 and v3 and so on, finding p4, p5, p6 and so on until the pk I found is the same as p1. Then, I connect all the points I found with straight lines.
The algorithm above may not be the most efficient one available for constructing the convex hull, but it works.
For more information on the convex hull, see this World of Mathematics article.
