A historical note on convex hull finding algorithms

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)21-28
Number of pages8
JournalPattern Recognition Letters
Volume3
Issue number1
DOIs
StatePublished - Jan 1985

Keywords

  • Algorithms
  • complexity
  • computational geometry
  • convex hull
  • monotone polygons
  • pattern recognition

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

Cite this