Computing the Convex Hull

1. Consider the 2-D problem of points {p1...pn} on the xy-axis. Let min be the index of the point with minimal x-value (if more than 1, pick the one with maximal y-value). Similarly, let max be the index of the point with maximal y-value of the set of points with maximal x-value.

2. Let T be the set of all points with x-values greater than x(pmin) and less than x(pmax), union with pmin and pmax.

3. Call CONNECT(min,max,T), which returns the sequence of indices of the points in the upper convex hull.

4. In a similar fashion, construct the lower convex hull.

5. Join upper and lower hulls together.