Brief Introduction

It is assumed that the reader is more or less familiar with the concept of convex hulls. For a detailed introduction to convex hulls please follow one of these links.

The Convex Hull of a polygon P is the smallest convex polygon which encloses P. Imagine that you have to run around P as fast as possible. The path you will choose (neglecting momentum) is the convex hull of P.

This page was designed to provide information about some of the most well known linear-time convex hull algorithms (correct and incorrect). I've tried to keep things informal and concentrate on the main ideas of each algorithm as opposed to minor details. Algorithms are listed in chronological order, so that you may almost "re-live" the convex hull story from beginning to present. Of course, this page also serves as a warning to all potential implementors of convex hull algorithms. There are many incorrect yet intuitive algorithms to be found in the literature.

If you find any of the descriptions in the following sections to be unclear, if you disagree with my comments, find small mistakes/omissions, or find other algorithms, please contact me.

The Quest for Linear time.

By 1978 it was known[2] that finding the convex hull of a set of points is Omega(nlogn), and straightforward algorithms for doing so had been presented. Clearly, such algorithms could be used to find the convex hull of any polygon, by considering only the coordinates of all vertices. It seemed reasonable though that the structure of simple polygons could provide enough information to reduce the complexity of finding convex hulls.

The first linear time algorithm was proposed by Sklansky in 1972 [1]. It was short and elegant. Unfortunately, it was also incorrect. The first correct algorithm was by McCallum and Avis in 1979 [3]. The algorithm generally accepted as the "best" so far was by Melkman in 1987 [19]. It seems unlikely that this algorithm will be surpassed.

A list of the algorithms that I have found is presented below, in chronological order by date of publication:

1972 Sklansky: Incorrect.

1975 Shamos: Incorrect.

1979 McCallum , Avis: Correct.

1980 Kim: Incorrect.

1982 Sklansky: Incorrect.

1983 Lee: Correct.

1983 Graham , Yao: Correct.

1983 ElGindy, Avis , Toussaint: Correct.

1983 Ghosh , Shyamasundar : Incorrect.

1984 Bhattacharya , ElGindy: Correct.

1985 Preparata and Shamos: Correct.

1985 Orlowski: Correct.

1986 Shin , Woo: Correct.

1986 Werner: Incorrect.

1987 Melkman: Correct.

1989 Chen: Incorrect.