ACM Transactions on Mathematical Software · 1977 · 290 citations · 3 references
ComputingComputer ScienceAlgorithmsComputational GeometryOptimizationApproximation AlgorithmsConvex AnalysisConvex GeometryConvex HullsConvex OptimizationConvex Hull Algorithms
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.
3