On Constructing Approximate Convex Hull

M. Zahid Hossain, M. Ashraful Amin

Computer Vision and Cybernetics Research Group, School of Engineering and Computer Science, Independent University, Dhaka, Bangladesh.

DOI: 10.4236/ajcm.2013.31A003                

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

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	J. Hu and H. Yan, “Polygonal Approximation of Digital Curves Based on the Principles of Perceptual Organization,” Pattern Recognition, Vol. 30, No. 5, 2006, pp. 701- 718. doi:10.1016/S0031-3203(96)00105-7
[2]	R. Bellman, B. Kashef and R. Vasudevan, “Mean Square Spline Approximation,” Journal of Mathematical Analysis and Applications, Vol. 45, No. 1, 1974, pp. 47-53. doi:10.1016/0022-247X(74)90119-X
[3]	J. T. Klosowski, M. Held, J. S. B. Mitchell, H. Sowizral, and K. Zikan, “Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs,” IEEE Transactions on Visualization and Computer Graphics, Vol. 4, No. 1, 1998, pp. 21-36. doi:10.1109/2945.675649
[4]	X. Zhang, Z. Tang, J. Yu and M. Guo, “A Fast Convex Hull Algorithm for Binary Image,” Informatica (Slovenia), Vol. 34, No. 3, 2010, pp. 369-376.
[5]	R. L. Graham, “An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set,” Information Processing Letters, Vol. 1, No. 4, 1972, pp. 132-133. doi:10.1016/0020-0190(72)90045-2
[6]	A. C.-C. Yao, “A Lower Bound to Finding Convex Hulls,” Journal of the ACM, Vol. 28, No. 4, 1981, pp. 780-787. doi:10.1145/322276.322289
[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, 1973, pp. 18-21. doi:10.1016/0020-0190(73)90020-3
[8]	F. P. Preparata and M. I. Shamos, “Computational Geometry: An Introduction,” Springer-Verlag Inc., New York, 1985.
[9]	D. G. Kirkpatrick and R. Seidel, “The Ultimate Planar Convex Hull Algorithm,” SIAM Journal on Computing, Vol. 15, No. 1, 1986, pp. 287-299. doi:10.1137/0215021
[10]	T. M. Chan, “Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions,” Discrete & Computational Geometry, Vol. 16, No. 4, 1996, pp. 361-368. doi:10.1007/BF02712873
[11]	A. A. Melkman, “On-Line Construction of the Convex Hull of a Simple Polyline,” Information Processing Letters, Vol. 25, No. 1, 1987, pp. 11-12. doi:10.1016/0020-0190(87)90086-X
[12]	J. L. Bentley, F. P. Preparata and M. G. Faust, “Approximation Algorithms for Convex Hulls,” Communications of the ACM, Vol. 25, No. 1, 1982, pp. 64-68. doi:10.1145/358315.358392
[13]	E. Soisalon-Soininen, “On Computing Approximate Convex Hulls,” Information Processing Letters, Vol. 16, No. 3, 1983, pp. 121-126. doi:10.1016/0020-0190(83)90062-5
[14]	L. Kavan, I. Kolingerova and J. Zara, “Fast Approximation of Convex Hull,” Proceedings of the 2nd IASTED International Conference on Advances in Computer Science and Technology, ACTA Press, Anaheim, 2006, pp. 101-104.
[15]	J. O’Rourke, “Computational Geometry in C,” 2nd Edition, Cambridge University Press, New York, 1998. doi:10.1017/CBO9780511804120
[16]	H. Edelsbrunner and E. P. Mücke, “Simulation of Simplicity: A Technique to Cope with Degenerate Cases in Geometric Algorithms,” ACM Transactions on Graphics, Vol. 9, No. 1, 1990, pp. 66-104. doi:10.1145/77635.77639
[17]	I. Z. Emiris, J. F. Canny and R. Seidel, “Efficient Perturbations for Handling Geometric Degeneracies,” Algorithmica, Vol. 19, No. 1-2, 1997, pp. 219-242. doi:10.1007/PL00014417