On Constructing Approximate Convex Hull

Authors: M. Zahid Hossain, M. Ashraful Amin

Abstract:

The algorithms of convex hull have been extensively studied in literature, principally because of their wide range of applications in different areas. This article presents an efficient algorithm to construct approximate convex hull from a set of n points in the plane in O(n + k) time, where k is the approximation error control parameter. The proposed algorithm is suitable for applications preferred to reduce the computation time in exchange of accuracy level such as animation and interaction in computer graphics where rapid and real-time graphics rendering is indispensable.

Keywords: Convex hull, Approximation algorithm, Computational geometry, Linear time.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1087852

References:

[1] R. Bellman, B. Kashef, and R. Vasudevan, “Mean square spline approximation,” Journal of Mathematical Analysis and Applications, vol. 45, no. 1, pp. 47–53, 1974.
[2] J. Hu and H. Yan, “Polygonal approximation of digital curves based on the principles of perceptual organization,” Pattern Recognition, vol. 30, no. 5, pp. 701–718, 2006.
[3] J. T. Klosowski, M. Held, J. S. B. Mitchell, H. Sowizral, and K. Zikan, “Efficient collision detection using bounding volume hierarchies of kdops,” IEEE Transactions on Visualization and Computer Graphics, vol. 4, pp. 21–36, January 1998.
[4] X. Zhang, Z. Tang, J. Yu, and M. Guo, “A fast convex hull algorithm for binary image,” Informatica (Slovenia), vol. 34, no. 3, pp. 369–376, 2010.
[5] R. L. Graham, “An efficient algorithm for determining the convex hull of a finite planar set,” Information Processing Letters, vol. 1, no. 4, pp. 132–133, 1972.
[6] A. C.-C. Yao, “A lower bound to finding convex hulls,” J. ACM, vol. 28, pp. 780–787, October 1981.
[7] R. A. Jarvis, “On the identification of the convex hull of a finite set of points in the plane,” Information Processing Letters, vol. 2, no. 1, pp. 18–21, 1973.
[8] F. P. Preparata and M. I. Shamos, Computational geometry: an introduction. New York, NY, USA: Springer-Verlag New York, Inc., 1985.
[9] D. G. Kirkpatrick and R. Seidel, “The ultimate planar convex hull algorithm,” SIAM Journal on Computing, vol. 15, pp. 287–299, February 1986.
[10] T. M. Chan, “Optimal output-sensitive convex hull algorithms in two and three dimensions,” Discrete & Computational Geometry, vol. 16, no. 4, pp. 361–368, 1996.
[11] A. A. Melkman, “On-line construction of the convex hull of a simple polyline,” Information Processing Letters, vol. 25, pp. 11–12, April 1987.
[12] J. L. Bentley, F. P. Preparata, and M. G. Faust, “Approximation algorithms for convex hulls,” Communications of the ACM, vol. 25, pp. 64–68, January 1982.
[13] E. Soisalon-Soininen, “On computing approximate convex hulls,” Information Processing Letters, vol. 16, no. 3, pp. 121–126, 1983.
[14] L. Kavan, I. Kolingerova, and J. Zara, “Fast approximation of convex hull,” in Proceedings of the 2nd IASTED international conference on Advances in computer science and technology. Anaheim, CA, USA: ACTA Press, 2006, pp. 101–104.
[15] J. O’Rourke, Computational geometry in C (2nd ed.). New York, NY, USA: Cambridge University Press, 1998.
[16] H. Edelsbrunner and E. P. M¨ucke, “Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms,” ACM Transactions on Graphics, vol. 9, pp. 66–104, January 1990.
[17] I. Z. Emiris, J. F. Canny, and R. Seidel, “Efficient perturbations for handling geometric degeneracies.” Algorithmica, vol. 19, no. 1/2, pp. 219–242, 1997.