Connect(k,m,S)

Main Convex Hull Algorithm

1a. Let A be the median x-value of S, and L be the median line with x-value=A.

2a. Let I and J be the indices of points contained in a supporting line of S, such that x(pI) is less than or equal to A, and x(pJ) is greater than A.

3a. Let Sleft be the set of points of S with x-values less than x(pI), union with pI. Similarly let Sright contain the points in S with x-values greater than x(pJ), union with pJ.

4a. If I=k, output I...else call CONNECT(k,I,Sleft).

5a. If J=m, output J...else call CONNECT(J,m,Sright).