A New Convex Hull Algorithm for Planar Sets

William F. Eddy

ACM Transactions on Mathematical Software · 1977 · 290 citations · 3 references

DOIFull text

Open access

Concepts

Abstract

A new algorithm, CONVEX, that determines which points of a planar set are vertices of the convex hull of the set is presented. It is shown that CONVEX operates in a fashion similar to the sorting algorithm QUICKERSORT. Evidence is given which indicates that in some situations CONVEX is preferable to earlier algorithms. A Fortran implementation, intended to minimize execution time, is presented and an alternative, which minimizes storage requirements, is discussed.

References

3