Jarvis' March
This is perhaps the most simple-minded algorithm for the
convex hull, and yet in some cases it can be
very fast. The basic idea is as follows:
- Start at some extreme point, which is guaranteed to be on the hull.
- At each step, test each of the points, and find the one which
makes the largest right-hand turn. That point has to be the next
one on the hull.
Because this process marches around the hull in counter-clockwise order,
like a ribbon wrapping itself around the points,
this algorithm also called the "gift-wrapping" algorithm.
Here's a demonstration of Jarvis' march, on a set of 30 random points.
Click here if you need instructions on
using the applet.
As we can see, the algorithm is not very fast in this case.
Quick-hull would probably be faster. In fact
if n points are arranged in a circle, Jarvis' march will
take time proportional to n^2, as you can see in the following
demo:
If you think about it, you'll see that Jarvis' march takes time
proportional to
nh, where n is the number of input points, and
h is the number of points on the hull. In other words,
Jarvis' march is output-sensitive. The algorithm works best
for inputs such as the following, where h is 3:
Alejo Hausner, CS Department, Princeton University
Last modified: Sat Feb 27 16:30:36 EST 1999