Convex Hulls
What is the convex hull of a set of points? This can be answered two ways:
- Formally: It is the smallest convex set containing the points.
- Informally: It is a rubber band wrapped around the "outside"
points.
In the example below, the convex hull of the blue points is the black
line that contains them.
Try moving the points around, to see how the hull changes.
To gain some insight, try the following:
- move a point which is a vertex of the hull
- choose a point inside the hull, and move it outside.
- rearrange the points to get a convex hull with as few edges
as possible. What is the minimum possible number of edges?
How do we compute the convex hull of a set of points? There are many ways.
Here are a few:
Alejo Hausner, CS Department, Princeton University
Last modified: Wed Jul 17 14:40:48 1996