Journal Article2013Cited by 10

On constructing approximate convex hull

M Zahid Hossain, M Ashraful Amin

American Journal of Computational Mathematics

Scientific Research Publishing, Inc., Vol. 3, Issue 01, pp. 11–17, ISBN: 2161-1203

DOI: 10.4236/ajcm.2013.31a003Open AccessURL

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 construction
  • Computer graphics
  • Real-time rendering
  • linear-time algorithms
  • planar point sets
  • approximation error

CCDS Authors

Prof. M Ashraful Amin, PhD
M Ashraful Amin, PhD

Prof. M Ashraful Amin, PhD

  • Founder Director, CCDS
  • Director, AI/ML, HCI & DS Wings

Professor

+1 more affiliation

Department of Information Sciences and Technology

George Mason University, USA

Published at

ACL, CHI, UbiComp, ECAI, WACV, PAKDD, IJCNN, ICPR, ICIP, HCII, CLEF, BLP, Scientific Reports, JMIR, IEEE Access, Smart Agricultural Technology, Frontiers in Computational Neuroscience, Diabetes Research and Clinical Practice, PLOS ONE

Research Interests

Machine Learning, Cognitive & Vision Science, Cybernetics, Surveillance & Security, ICT in Education, Health, & Agriculture, Human-Computer Interaction, Internet of Things, Robotics

References

  1. 1.Franco P. Preparata, Michael Ian Shamos. (1985). Computational Geometry. [10.1007/978-1-4612-1098-6]
  2. 2.Franco P. Preparata, Michael Ian Shamos. (1985). Computational geometry. an introduction.
  3. 3.Ronald Graham. (1972). An efficient algorith for determining the convex hull of a finite planar set. Information Processing Letters, 1(4), 132–133[10.1016/0020-0190(72)90045-2]
  4. 4.Joseph O’Rourke, A. John Mallinckrodt. (1995). Computational Geometry in C. Computers in Physics, 9(1), 55[10.1063/1.4823371]
  5. 5.James T. Klosowski, Martin Held, Joseph S. B. Mitchell, Henry A. Sowizral, Karel Zikan. (1998). Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Transactions on Visualization and Computer Graphics, 4(1), 21–36[10.1109/2945.675649]
  6. 6.Joseph O’Rourke. (1998). Computational Geometry in C. Cambridge University Press eBooks[10.1017/cbo9780511804120]
  7. 7.Herbert Edelsbrunner, Ernst P. Mücke. (1990). Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics, 9(1), 66–104[10.1145/77635.77639]
  8. 8.R.A. Jarvis. (1973). On the identification of the convex hull of a finite set of points in the plane. Information Processing Letters, 2(1), 18–21[10.1016/0020-0190(73)90020-3]
  9. 9.David Kirkpatrick, Raimund Seidel. (1986). The Ultimate Planar Convex Hull Algorithm?. SIAM Journal on Computing, 15(1), 287–299[10.1137/0215021]
  10. 10.Timothy M. Chan. (1996). Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry, 16(4), 361–368[10.1007/bf02712873]
  11. 11.Avraham A. Melkman. (1987). On-line construction of the convex hull of a simple polyline. Information Processing Letters, 25(1), 11–12[10.1016/0020-0190(87)90086-x]
  12. 12.Joseph O’Rourke. (1998). Computational geometry in C (2nd ed.). Cambridge University Press eBooks
  13. 13.Andrew Chi-Chih Yao. (1981). A Lower Bound to Finding Convex Hulls. Journal of the ACM, 28(4), 780–787[10.1145/322276.322289]
  14. 14.Selim G. Akl, Godfried T. Toussaint. (1978). A fast convex hull algorithm. Information Processing Letters, 7(5), 219–222[10.1016/0020-0190(78)90003-0]
  15. 15.Jon Bentley, Franco P. Preparata, Mark G. Faust. (1982). Approximation algorithms for convex hulls. Communications of the ACM, 25(1), 64–68[10.1145/358315.358392]
  16. 16.Xianquan Zhang, Zhenjun Tang, Jinhui Yu, Mingming Guo. (2010). A Fast Convex Hull Algorithm for Binary Image. , 34(3), 369–376[10.31449/inf.v34i3.311]
  17. 17.Ioannis Z. Emiris, John Canny, Raimund Seidel. (1997). Efficient Perturbations for Handling Geometric Degeneracies. Algorithmica, 19(1-2), 219–242[10.1007/pl00014417]
  18. 18.Ladislav Kavan, Ivana Kolingerová, Jiřı́ Žára. (2006). Fast approximation of convex hull. , 101–104
  19. 19.Hawing Hu, Hong Yan. (1997). Polygonal approximation of digital curves based on the principles of perceptual organization. Pattern Recognition, 30(5), 701–718[10.1016/s0031-3203(96)00105-7]
  20. 20.Eljas Soisalon-Soininen. (1983). On computing approximate convex hulls. Information Processing Letters, 16(3), 121–126[10.1016/0020-0190(83)90062-5]
  21. 21.Richard Bellman, B. G. Kashef, R. Vasudevan. (1974). Mean square spline approximation. Journal of Mathematical Analysis and Applications, 45(1), 47–53[10.1016/0022-247x(74)90119-x]

Cited By

  1. 1.Xiaoqing Gu, Fu-lai Chung, Shitong Wang. (2018). Fast convex-hull vector machine for training on large-scale ncRNA data classification tasks. Knowledge-Based Systems, 151, 149–164[10.1016/j.knosys.2018.03.029]
  2. 2.Andrea Zanette, Alessandro Lazaric, Mykel J. Kochenderfer, Emma Brunskill. (2019). Limiting Extrapolation in Linear Approximate Value Iteration. Neural Information Processing Systems, 32, 5615–5624
  3. 3.Artem Potebnia, Sergiy Pogorilyy. (2015). Innovative GPU accelerated algorithm for fast minimum convex hulls computation. Annals of Computer Science and Information Systems, 5, 555–561[10.15439/2015f305]
  4. 4.Artem Potebnia, Sergiy Pogorilyy. (2016). Fast Output-Sensitive Approach for Minimum Convex Hulls Formation. Studies in computational intelligence, 1–20[10.1007/978-3-319-40132-4_1]
  5. 5.Yehezkel S. Resheff. (2016). Online trajectory segmentation and summary with applications to visualization and retrieval. , 33, 1832–1840[10.1109/bigdata.2016.7840801]
  6. 6.Tatsuma MORI, Taito MANABE, Yuichiro SHIBATA. (2021). A Hardware Oriented Approximate Convex Hull Algorithm and its FPGA Implementation. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E105.A(3), 459–467[10.1587/transfun.2021vlp0016]
  7. 7.Oscar Y Buitrago, Andrés L Ramírez, Rodrigo A Britto. (2015). Nuevo Algoritmo para la Construcción de la Envolvente Convexa en el Plano. Información tecnológica, 26(4), 137–144[10.4067/s0718-07642015000400017]
  8. 8.Pingxun Wang. (2022). A Convex Hull-Based Machine Learning Algorithm for Multipartite Entanglement Classification. Applied Sciences, 12(24), 12778[10.3390/app122412778]
  9. 9.Tatsuma Mori, Taito Manabe, Yuichiro Shibata. (2020). Fast and Memory Efficient Approximated Convex Hull Computation with FPGA. , 115, 174–180[10.1109/candar51075.2020.00031]
  10. 10.Tatsuma Mori, Daiki Furukawa, Keigo Motoyoshi, Haruto Ikehara, Kaito Ohira, Taito Manabe, Yuichiro Shibata, Tomohiro Ueno, Kentaro Sano. (2022). Stream Computation of 3D Approximate Convex Hulls with an FPGA. , 32, 69–75[10.1145/3535044.3535053]
← All publications