
The Convex Hull
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+(1l)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 = {p_{1},p_{2},...,p_{n}} is finite, is that the convex hull consists of all
points x which may be written
x = l_{1} p_{1} + l_{2} p_{2} + ... + l_{n} p_{n},
for some l_{1},l_{2},...,l_{n} such that
l_{1}+l+2+...+l_{n} = 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 p_{1} with the smallest x coordinate. Then, I chose
a vector v_{1} pointing up the y axis. Then I found the point p_{2}
for which the line p_{1}p_{2} made the smallest angle with v_{1}, and let
v_{2} be a vector in the direction of this line. Then, I used p_{2} and
v_{2} to find p_{3} and v_{3} and so on, finding p_{4}, p_{5}, p_{6} and
so on until the p_{k} I found is the same as p_{1}. 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. The actual source code is also available.
For more information on the convex hull, see this
World of Mathematics
article.
File translated from T_{E}X by T_{T}H, version 2.25.
