Chris
Harrison

Research
Curriculum Vitae
Fun Projects
Travel

An Investigation of Graham’s Scan and Jarvis’ March



Although the term “computational geometry” was coined in the mid-1970’s, geometry is one of the longest studied mathematical areas because of its enormous number of applications. With the advent of computers, which could perform millions of mathematical calculations per second, new topics and problems in geometry began to emerge and the field of computational geometry was born. As the subject evolved, a number of new applications became apparent, ranging from computer vision and geographical data analysis, to collision detection for robotics and molecular biology. Computational geometry also has several uses in higher mathematics including advanced set theory and graph theory. This paper discusses perhaps one of the oldest and most celebrated computational geometry problems; the convex hull. (O’Rourke, 70) (Sunday, A) (Toussaint, 23) (CG Impact Task Force)

A convex hull is the shape that completely encloses a set of points with the fewest number of perimeter nodes. There are two main properties of convex hulls that should be explored before introducing Graham’s Scan or Jarvis’ March. One of these properties is that all of the points in the final polygon must be indented outwards, or more formally, convex. If any points are concave, there exists a better path by excluding that point, and drawing a direct line between its two neighbor points, which reduces the overall perimeter point count by one, as can be seen in the figures below. This property is exploited by Graham’s Scan, a pioneering algorithm for convex hulls covered later in the paper. (Mulmuley, 41) (O’Rourke, 71) (Preparata, 91)

Another important property is that the most extreme point on any axis is part of the convex hull. This fact is apparent if you consider an example in which an extreme point is not in the convex hull. This would mean the perimeter of the convex hull passes through a point less extreme than that point. However, it is then obvious that the extreme point would not be included in the enclosed set, thus voiding a fundamental characteristic of convex hulls. This property is used by a number of algorithms because they rely on information computed from an initial point in the convex hull. (Preparata, 152) (O’Rourke, 73)

The birth of computational geometry is often credited to Ronald Graham’s research and subsequent 1972 paper titled “An efficient algorithm for determining the convex hull of a finite planar set.” His algorithm was a response to Bells Lab’s request for a faster algorithm. They had to determine the convex hull of ten thousand points rapidly, a challenging number in the late 1960s with existing O(n2) algorithms. Graham was hired and developed what is now known as Graham’s Scan, an O(nlogn) convex hull algorithm. (O’Rourke, 80) (Graham, 1) (Sunday, B) (Mulmuley, 57)

The first phase of the algorithm is to identify the minimal point on some axis. The y-axis is a good candidate, as the angles for all other points in the set range from 90° to 270°, which facilitates sorting. Once the minimal y-axis point has been located, and the remaining points sorted in increasing angular value, the main phase of Graham’s Scan can begin. The polygon starts as a perimeter to every point in the set (see figure below). As noted before, Graham’s Scan relies on the convexity of a point, relative to its neighbors, to determine if it is part of the convex hull. Starting at the second node in the perimeter (the first node clockwise after the minimal point), the algorithm systematically tests every point. If the point is convex, it proceeds to the next point. If the point is not convex (concave), it removes the current point from the perimeter list. The figure below illustrates this process. Blue lines represent the old, no longer existing edges. A new, green edge shows the connection between the once existent point’s neighbors. Rather than progressing as usual however, the algorithm needs to backtrack to the previous point to see if the change has caused other nodes to become convex. This process continues until having looped around the perimeter, back to the minimal point. Once this occurs, the points remaining in the perimeter list are nodes in the convex hull.

Jarvis’ March, which was published a year later than Graham’s paper, runs in O(nh) time, n being the number of points in the set, and h being the number of points in the convex hull. If every point in the set is also in the convex hull, Jarvis’ March will run in O(n2) time. The algorithm uses a technique called “gift wrapping,” which was first suggested by Chand and Kapur in 1970, after their research in computing convex hulls in arbitrary dimensions. This is a valuable algorithm when it is known that the convex hull will have few nodes in the perimeter set. For example, if the distribution of points was heavily clustered with a few extreme points that would comprise the outside perimeter. In real-world data, such distributions are not uncommon, and this method can capitalize on this attribute to compute the convex hull more rapidly. The algorithm’s concept is analogous to tying a string to a top most pin on a board, and wrapping the cord around the entire set of pins back to the first node. This is where the term “gift wrapping” originates. The shape of the cord would be the perimeter of the points in the set, or the convex hull. (O’Rourke, 77) (Sunday, B)

The implementation of Jarvis’ March is not as straightforward because we are working within the confines of programming languages. However, the physical intuition can be applied to design an algorithm approach. As with Graham’s Scan, Jarvis’ March must first locate a starting node in the convex hull. As noted before, the point with the minimum y-axis value is a good choice because the angles relative to other points in the set range from 90° to 270°. This makes identifying the point with the minimal angle, relative to the current point, considerably easier. Jarvis’ March must also locate the most extreme point on the y-axis as well. The use of this point will be discussed shortly. Starting with the minimal point, already known to be in the final perimeter, the algorithm scans all the points in the set, computes their angle, and stores the most angularly minimal point. Because the initial ordering of the set is arbitrary, it is necessary to scan all nodes in the set except for the current point. Sorting by angle is not useful, because the angles change as the algorithm progresses from point to point. The point found from the process described above will be the next point in the convex hull, in the clockwise direction. If you relate this to the physical example using the string and pins, it is evident that as you wrap the string around the set, the first pin that touches the string will be the one with the least relative angle.

Once the next point in the convex hull is identified, the process continues based on angles relative to the new point. It is important to note that when scanning the set for the next angularly minimal point, some points are ignored. This is because it is possible for some points to have the least angle relative to the new point and not be part of the convex hull. The next point in the convex hull must continue in the clockwise motion, or it would be a concave, and there would be a point with a lower angle relative to the prior point in the perimeter (see point labeled “impossible point”). In that case, the “impossible point” would have been selected to be in the convex hull. Points with angles less than the angle from the prior point relative to the current point are disregarded, since they would void the clockwise motion (see right figure). Such points cannot be part of the convex hull (see point labeled “invalid point”). Also note that this process ignores points already added to the convex hull as well. This process can be simplified to exclude points with angles less than 90°, since we are guaranteed the next point in the convex hull will not be in this angular range.

This entire process is repeated, hopping from point to point, until reaching the maximal y-axis point. At this stage, only the left-hand side of the convex hull has been computed. The same process starts again from the minimal y-axis node. However, instead of locating the point with the least angular value, the algorithm scans for the greatest angular value. This point is also part of the perimeter, however, now the algorithm is computing the right-hand side of the convex hull. As before, precautions have to be made to exclude points not continuing in the counterclockwise motion. This process can be simplified to exclude points with angles greater than 270°. Once the algorithm reaches the max y-axis point, the algorithm and convex hull is complete.

Early convex hull algorithms, like the two discussed in this paper, are still interesting and useful today, and provide a unique insight into the birth of the field. There have been several advances since 1973, which has yielded new convex hull algorithms. The first O(nlogh) algorithm was proposed by Preparata and Hong in 1977, which is faster than both Graham’s Scan (assuming h<n) and Jarvis’ March, and used a clever divide and conquer approach. Eight other O(nlogh) algorithms have been suggested since then: Andrew’s monotone chain in 1977, Graham and Yao's sweep-line in 1982, Kallay’s incremental method in 1984, Kirkpatrick and Seidel’s marriage-before-conquest in 1986, Chan's shatter-hull in 1996, Chan, Snoeyink and Yap's prune and search in 1997, Bhattacharya and Sen's pruned randomized quickhull in 1997, and lastly Wenger’s randomized quick hull in 1997. Explaining how these algorithms work is beyond the scope of this paper. However, it does highlight the ongoing work in the field. New problems relating to convex hulls have also emerged. For example, the convex layers problem, where sets of points can be organized into layers, much like an onion, where each layer is a convex hull of the points within it. Rapidly computed approximate convex hulls are also a focus of research. Convex hulls are applicable to points in arbitrary dimensions, so most algorithms have been extended to operate in higher dimensions, which has also generated a lot of new and interesting problems. The list of applications will surely grow, and with it, a new generation of computer scientists to study convex hulls. (Sunday, B) (Preparata, 149, 166) (O’Rourke, 111) (Sack, 164)


Implementation Notes

The overall algorithmic procedures are covered in the main paper. The code is heavily commented; please refer to the code for exact algorithmic operation.

Graham’s Scan

The points are stored in increasing angular order with respect to the minimal y-axis point. Because of the variable number of points in the set and the fact that Graham’s Scan progressively removes points from the polygon, a double linked list seemed like an obvious choice because of it’s dynamic behavior in memory. This list is also circular, so that traversing the nodes will return to the minimal y-axis point. When a point is found to be convex, the node can simply be deleted, and the prev and next pointers of the neighbor nodes can be adjusted accordingly to point to each other. Helper function such as isConvexPoint(…) and findAngle(…) help abstract much of the complexity out of the main Graham’s Scan procedure.

Jarvis’ March

The points are stored in a fixed array of size one thousand. However, this can be easily changed to whatever value is desired. A static sized contiguous array is an appropriate data structure because of the algorithm’s sequential and repetitious point checking. Searching operations would be considerably slower assuming non-contiguous memory allocation of nodes in a linked list. Using a static array makes it far more likely the data with be brought into cache, where operations can happen considerably faster. Using arrays and index values is also easier and less prone to bugs. Helper function such as addUsedPoint(…) and findAngle(…) help abstract much of the complexity out of the main Jarvis’ March procedure.

Graphics

Graphics are generated by calls to the Simple DirectMedia Layer library (SDL Lib). A 3rd party extension library was used to provide primitive drawing functions, such as circles and lines. SDL also handles user input. Users can hit the space bar to randomly create, draw, and compute new convex hulls. A delay of one hundred milliseconds was added into the primary graphics loop to allow users to see the rendition before the program generates a new convex hull. The escape key terminates the program.


Application Notes

Graham’s Scan

Blue lines are used to indicate point-to-point comparisons. These occur in two phases of the algorithm: during the initial point sorting (by angle) and testing convexity on points by comparing the relative angles of their neighbors. As Graham’s Scan proceeds from point to point, it removes convex points from the polygon. If a point is removed, a blue line is drawn to represent the new shape.

Red lines indicate the original shape of the polygon before Graham’s Scan. As you can see, a number of the points are convex. These will be incrementally removed as Graham scan progresses. A blue line is drawn to show the new polygon.

Green lines show the final perimeter of the convex Hull. There are blue lines also reflecting the completed polygon, but they are not shown.

Jarvis’ March (Gift Wrapping)

Blue lines represent point-to-point comparisons. As Jarvis’ March progresses around the convex hull, it finds the point with the most minimal or maximal angle relative to itself; that is the next point in the convex hull. As you can see, blue lines radiate from every point in the completed polygon. This is because the algorithm tests every point in the set at every node in the convex hull. Although not visible, blue lines also show tests between neighbor points. However, because those edges are part of the perimeter of the convex hull, a green line covers them.


References

  • CG Impact Task Force. Application Challenges to Computational Geometry. Technical Report TR-521-96. Princeton University, April 1996.
  • Mulmuley, Ketan. Computational Geometry: An Introduction Through Randomized Algorithms. Englewood Cliffs, NJ, Prentice-Hall Inc., 1994.
  • O’Rourke, Joseph. Computational Geometry in C. Cambridge: Cambridge University Press, 1994.
  • Preparata, Franco P. and Michael Ian Shamos. Computational Geometry; An Introduction. New York: Springer-Verlag New York Inc., 1985.
  • Ed. Sack, J. R. and J. Urrutia. Handbook of Computational Geometry. New York, Elsevier Science Publishers, 2000.
  • Sunday, Daniel. Overview. Dec 2003. (A) http://geometryalgorithms.com/overview.htm
  • Sunday, Daniel. Convex Hull of a 2D Point Set or Polygon. Dec 2003. (B) http://geometryalgorithms.com/Archive/algorithm_0109/algorithm_0109.htm
  • Ed. Toussaint, G. Machine Intelligence and Pattern Recognition 2; Computational Geometry. New York, Elsevier Science Publishers, 1985.

Downloads

Graham's Scan - C++ Source Code

Jarvis' March - C++ Source Code

C99 - C Source Code (adapted from Graham's code by Ben Brame)

(Both require SDL libraries for graphical content)

© Chris Harrison