TY - GEN
T1 - Analysis of a simple yet efficient convex hull algorithm
AU - Golin, Mordecai
AU - Sedgewick, Robert
N1 - Funding Information:
Convex hull algorithms can be seen as performing two separate tasks: The first is identifying those points actually on the hull, the second is eliminating those inside of it. Alternatively these 1This work supported in part by NSF Grant DCR-8605962 and Office of Naval Research Grant N00014-87-K-0460.
Publisher Copyright:
© 1988 ACM.
PY - 1988/1/6
Y1 - 1988/1/6
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85013527084&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85013527084&partnerID=8YFLogxK
U2 - 10.1145/73393.73409
DO - 10.1145/73393.73409
M3 - Conference contribution
AN - SCOPUS:85013527084
T3 - Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988
SP - 153
EP - 163
BT - Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988
PB - Association for Computing Machinery, Inc
T2 - 4th Annual Symposium on Computational Geometry, SCG 1988
Y2 - 6 June 1988 through 8 June 1988
ER -