An optimal real-time algorithm for planar convex hulls

ABSTRACT

An algorithm is described for the construction in real-time of the convex hull of a set of n points in the plane. Using an appropriate data structure, the algorithm constructs the convex hull by successive updates, each taking time O(log n), thereby achieving a total processing time O(n log n).

REFERENCES

• 1: Graham, R.L. An efficient algorithm for determining the convex hull of a finite planar set. Inform. Processing Letters 1 (1972), 132- 133.
• 2: Jarvis, R.A. On the identification of the convex hull of a finite set of points in the plane. Inform. Processing Letters 2 (1973), 18-21.
• 3: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 4: F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
• 5: Shamos, M.I. Problems in computational geometry. Dept. of Comptr. Sci., Yale U., New Haven, Conn., May 1975.
• 6: Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803772]
• 7: Shamos, M.1. Computational geometry. Dept. Comptr. Sci., Yale U., New Haven, Conn., 1977 (to be published by Springer Verlag).

INDEX TERMS

Keywords:
computational geometry, convex hull, on-line algorithms, planar set of points, real-time algorithms