Analysis of a simple yet efficient convex hull algorithm

ABSTRACT

This paper is concerned with a simple, rather intuitive preprocessing step that is likely to improve the average-case performance of any convex hull algorithm. For n points randomly distributed in the unit square, we show that a simple linear pass through the points can eliminate all but &Ogr;(√n) of the points by showing that a simple superset of the remaining points has size c√n + &ogr;(√n). We give a full implementation of the method, which should be useful in any practical application for finding convex hulls. Most of the paper is concerned with an analysis of the number of points eliminated by the procedure, including derivation of an exact expression for c. Extensions to higher dimensions are also considered.

REFERENCES

• BS: J.L. Bentley and M.I. Shamos, "Divide and Conquer for Linear Expected Time," Information Processing Letters 7(2) (Feb. 1978) 87-91.
• DT: L. Devroye and G.T. Toussaint, "A Note on Linear Expected Time Algorithms for Finding Convex Hulls," Computing, 26 (1981) 361-366
• Ed: William F. Eddy, A New Convex Hull Algorithm for Planar Sets, ACM Transactions on Mathematical Software (TOMS), v.3 n.4, p.398-403, Dec. 1977 [doi>10.1145/355759.355766]
• GS: G.R. Grimmet and D.R. Stirzaker, Probability and Random Processes, Clarendon Press, Oxford. (1985).
• OL: M.H. Overmars and J. van Leeuwen, "Further Comments on Bvkat's Convex Hull Algorithm," Information Processing Letters, 10(4,5) (July 1980) 209-212.
• PS: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• RS: A. R~nyi and R. Sulanke Ueb.r die kon vexe Hulle yon n zufallig gewahlten Punkten. I," Z. Wahrschien, 2 (1963) 75-84.
• Ru: W. Rudin, Principles of Mathematical Analysis, 3d ed., McGraw Hill, New York. (1976).
• Se: Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures

  G. Mathematics of Computing

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Measurement, Performance, Theory