Analysis of a simple yet efficient convex hull algorithm

Mordecai Golin, Robert Sedgewick

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

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 O(√n) of the points by showing that a simple superset of the remaining points has size c√n + o(√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.

Original languageEnglish (US)
Title of host publicationProceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988
PublisherAssociation for Computing Machinery, Inc
Pages153-163
Number of pages11
ISBN (Electronic)0897912705, 9780897912709
DOIs
StatePublished - Jan 6 1988
Event4th Annual Symposium on Computational Geometry, SCG 1988 - Urbana-Champaign, United States
Duration: Jun 6 1988Jun 8 1988

Publication series

NameProceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988

Other

Other4th Annual Symposium on Computational Geometry, SCG 1988
CountryUnited States
CityUrbana-Champaign
Period6/6/886/8/88

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Fingerprint Dive into the research topics of 'Analysis of a simple yet efficient convex hull algorithm'. Together they form a unique fingerprint.

  • Cite this

    Golin, M., & Sedgewick, R. (1988). Analysis of a simple yet efficient convex hull algorithm. In Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988 (pp. 153-163). (Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988). Association for Computing Machinery, Inc. https://doi.org/10.1145/73393.73409