What is the convex hull of a set of points? This can be answered two ways:
In the example below, the convex hull of the blue points is the black
line that contains them.
- Formally: It is the smallest convex set containing the points.
- Informally: It is a rubber band wrapped around the "outside"
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