# 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 on "Run" to start the demo.

*** SORRY! You need a java-enabled browser to run this applet. Otherwise, you'll only see this text. ***

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:

*** SORRY! You need a java-enabled browser to run this applet. Otherwise, you'll only see this text. ***

If you think about it, 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:

*** SORRY! You need a java-enabled browser to run this applet. Otherwise, you'll only see this text. ***

Alejo Hausner, CS Department, Princeton University
Last modified: Wed Jul 17 14:47:54 1996