On Constructing Approximate Convex Hull

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.

• M. Zahid Hossain
• M. Ashraful Amin

• Convex hull
• Approximation algorithm
• Computational geometry
• Linear time.

<p>[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.</p>