A historical note on convex hull finding algorithms

Most of the progress made on the convex hull problem has been accomplished during and after the late 1970's. In the convex hull literature to date, Graham (1972) is credited with the first optimal O(n log n) algorithm for computing the convex hull of n points on the plane. In this note we bring to light a hidden and forgotten convex hull algorithm due to Bass and Schubert (1967). Although their description of the algorithm is somewhat vague and, as described, their algorithm is incorrect, it is shown here that their procedure nevertheless contains most of the key ideas that have appeared in the convex hull literature in recent years. Finally, although the authors did not provide either a proof of correctness or a complexity analysis, it is shown here that a suitable interpretation of their algorithm runs correctly in O(n log n) time and thus predates Graham's algorithm by five years.