Project for CS507 - Computational Geometry  (Prof. Godfried T. Toussaint)
Presented by  Greg Aloupis & Bohdan Kaluzny
Other students projects can be found here.

Introduction

We present one of the simplest algorithms used to find the convex hull of a simple polygon.  Some basic definitions are provided for readers inexperienced in the field of Computational Geometry.  Our interactive Applet demonstrates the algorithm and provides a challenging puzzle for beginners.
 

Definitions
 

• A polygon is a closed path of straight line segments in R². These segments are also called edges of the polygon, and the intersection of two adjacent edges is a vertex of the polygon. Thus every polygon with n vertices has n edges.

• A simple polygon is one which has no intersecting non-adjacent edges (see Fig.1). Every simple polygon divides R² into an interior and an exterior region.

• A simple polygon is convex if the internal angle formed at each vertex is smaller than 180^o. If one were to walk along the polygon's path, one would make only right turns (or only left turns) at each vertex (see Fig.2).

• The convex hull of a polygon P is the smallest-area convex polygon which encloses P. Informally, it is the shape of a rubber-band stretched around P  (see Fig.3). Similarly, the convex hull of a set of points S is the smallest-area polygon which encloses S.  Note : the convex hull of a convex polygon P is P itself.

As you can see, you can visually construct the convex hull by filling in all the exterior "pockets" of P.

Algorithms
  The 3-coins algorithm was developed independently by Graham and Sklansky in 1972, to find convex hulls.

1. Graham's algorithm (a.k.a. Graham Scan)

Graham proposed using the 3-coins algorithm to find the convex hull of a set of n points in R².
Here is a simplified version: (see Fig.4 for an example)
 

1. Find an extremal point (for example, the point with smallest y coordinate) and label it p0.  2. Sort the remaining n-1 points radially, using p0 as the origin.   3. Place three coins on vertices p0, p1, p2 and label them "back", "center", and "front" respectively. (They will form a right turn from "back" to "front").   4. Do :  If  the 3 coins form a right turn (or if the 3 coins lie on collinear vertices),    - Take "back", place it on the vertex ahead of "front".    -  Relabel : "back" becomes "front", "front" becomes "center", "center" becomes "back".  Else (the 3 coins form a left hand turn)    - Take "center", place it on the vertex behind "back".    - Remove (or ignore hereafter) the vertex that "center" was on.    - Relabel : "center" becomes "back", "back" becomes "center".      Until  "front" is on vertex p0 (our start vertex) and the 3 coins form a right turn. 5. Connect the remaining points in order. This forms the convex hull of the original set of n points.

As you can see in Fig.4, the three coins advance along the ordered vertices, as long as they keep forming right had turns. If this were to continue till the end, the algorithm would have merely verified that the ordered vertices form a convex polygon.

As soon as a left hand turn is encountered (ex: vertices p₃,p₄,p₅), we know that it can't possibly be part of the convex hull, by definition. The "guilty" point p₄ is removed, so we must backtrack one step and re-establish that p₃ is a right hand turn by placing the coins on p₂,p₃,p₅. In our case p3 is no longer a right hand turn, so it too must be removed. Thus we backtrack again, check p₁,p₂,p₅, and continue.

A proof of correctness is provided below.

Complexity:
Since a vertex is deleted every time we backtrack one step, it is apparent that there is a maximum of n backtracks. So conceivably, we could get n loop iterations + n backtracks = 2n coin placements. Each coin placement requires a constant amount of work (locating next vertex, calculating angle, relabeling), so the running time of the 3-coins loop is O(n). It is well known that sorting is O(nlogn) (and Omega(nlogn)), so the overall run-time is dominated by sorting :

The time complexity of the Graham Scan is worst case optimal:  Theta(nlogn).

Since we are interested in computing the convex hull of a simple polygon, we now know that the least that could be done would be to re-sort the vertices radially about an extremal vertex, and apply the Graham Scan.
 

2. Sklansky's algorithm (a.k.a. Sklansky Scan)

Sklansky proposed using the 3-coins algorithm to find the convex hull of a simple n-polygon (in R²):
 

1. Find an convex vertex and label it p0.  2. Label the remaining n-1 vertices in a clockwise order, starting at p0   3. Place three coins on vertices p0, p1, p2 and label them "back", "center", and "front" respectively.   4. Do :  If  the 3 coins form a right turn (or if the 3 coins lie on collinear vertices),    - Take "back", place it on the vertex ahead of "front".    -  Relabel : "back" becomes "front", "front" becomes "center", "center" becomes "back".  Else (the 3 coins form a left hand turn)    - Take "center", place it on the vertex behind "back".    - Remove (or ignore hereafter) the vertex (and associated edges) that "center" was on.    - Relabel : "center" becomes "back", "back" becomes "center".      Until  "front" is on vertex p0 (starting vertex) and the 3 coins form a right turn. 5. The remaining vertices and edges form the convex hull of the original simple n-polygon .

Sklansky proposed that the structure present in a simple polygon would allow the computation of the convex hull to be carried out in O(n) time. Since sorting would not be needed, time complexity would be dominated by the 3-coins loop, which is linear. However, in 1978 it was shown by Bykat that the Sklansky Scan does not always work.

You may attempt to disprove Sklansky's proposal by providing a counterexample in our Applet. Just draw a simple polygon which will cause the Applet to find an incorrect convex hull. Try to use as few as six vertices. (Hint)
 

If you give up, you may view our counterexamples on the Applet.

Applet