Implementation of algorithms to compute the Convex Hull

Authors

DOI:

https://doi.org/10.31908/19098367.2668

Keywords:

Computational Geometry, Covex Hull, Gift Wrapping, Graham Scan, QuickHull

Abstract

Computational geometry is a discipline focused on solving problems in the geometric domain. In this context, the algorithm for computing the convex polygon called Convex Hull (CH) is important, because it is the basis for many other algorithms. The objective of the research was to implement algorithms that compute the CH incorporating modifications to reduce the execution time. The research started with a bibliographic review of computational geometry and the algorithms highlighted in the calculation of CH. Subsequently, the QuickHull, Gift Wrapping, and Graham Scan algorithms were implemented in JAVA in their original versions; some versions with modifications were also implemented. Upon completion of implementation, tests were run to verify the execution times. Finally, the QuickHull algorithm was found to be the fastest among the implementations performed in this research. It is also noted a reduction in execution times in the modified implementations in relation to the original ones of the Gift Wrapping and Graham Scan algorithms.

Author Biographies

  • Christian Andrés Candela Uribe., Universidad del Quindío, Universidad Tecnológica de Pereira

    Estudiante del Doctorado en Ingeniería con énfasis en Ciencias de la Computación de la Universidad Tecnológica de Pereira. Profesor Asociado en la Universidad del Quindío Colombia. Sus áreas de interés son: Arquitectura de Software, Ingeniería de Software y Microservicios.

  • Julio César Chavarro Porras, Universidad Tecnológica de Pereira

    Doctorado en Ingeniería con énfasis en Ciencias de la Computación de la Universidad del Valle. Profesor Asociado en la Universidad Tecnológica de Pereira Colombia. Sus áreas de interés son: Inteligencia Artificial, Arquitectura de Software, Ingeniería de Software y Bases de Datos.

  • Carlos Augusto Meneses Escobar, Universidad Tecnológica de Pereira

    Estudiante del Doctorado en Ingeniería con énfasis en Ciencias de la Computación de la Universidad Tecnológica de Pereira. Profesor Asistente en la Universidad Tecnológica de Pereira Colombia. Sus áreas de interés son: Inteligencia Artificial, Arquitectura de Software, Ingeniería de Software y Bases de Datos.

  • John Alexander Sanabria Ordoñez, Universidad del Valle

    Doctorado en Computer Information Science and Enginnering de la Universidad de Puerto Rico. Profesor Asistente en la Universidad del Valle Colombia. Sus áreas de interés son: Redes de computadores, Sistemas Distribuidos, Grid Computing y Plataformas Computacionales.

References

S. Bu-Qing and L. Ding-Yuan, Computational geometry: curve and surface modeling. Elsevier, 2014.

M. A. Jayaram and H. Fleyeh, "Convex Hulls in Image Processing: A Scoping Review," American Journal of Intelligent Systems, Artikel PeerReviewed no. 2, p. 48, 2016. [Online].

O. Y. Buitrago, A. L. Ramírez, and R. A. Britto, "Nuevo Algoritmo para la Construcción de la Envolvente Convexa en el Plano," New Algorithm to Construct a Planar Convex Hull., Article vol. 26, no. 4, pp. 137-144, 2015, doi: 10.4067/S0718-07642015000400017.

Y. Xu and W. Hou, "Calculation of operational domain of virtual maintenance based on convex hull algorithm," ed: IEEE, 2017, p. 1.

J. F. Peters, "Foundations of computer vision," ed: Springer International Publishing: 2017.

R. Xu, H. Dai, F. Wang, and Z. Jia, "A convex hull based optimization to reduce the data delivery latency of the mobile elements in wireless sensor networks," in 2013 IEEE 10th International Conference on High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing, 2013: IEEE, pp. 2245-2252.

H. Brönnimann, J. Iacono, J. Katajainen, P. Morin, J. Morrison, and G. Toussaint, "Space-efficient planar convex hull algorithms," Theoretical Computer Science, vol. 321, no. 1, pp. 25-40, 2004.

Z. Qihai, "New serial and parallel algorithms for finding convex hull based on clusters, domains and directions from single to multitude," Journal of Algorithms & Computational Technology, vol. 3, no. 2, pp. 191-227, 2009.

H.-Y. CHIANG, "Solving 2D Convex Hull with Parallel Algorithms," 2010.

N.-D. Hoang and N. K. Linh, "Quicker than Quickhull," Vietnam Journal of Mathematics, vol. 43, no. 1, pp. 57-70, 2015, doi: 10.1007/s10013-014-0067-1.

V. Skala, M. Smolik, and Z. Majdisova, "Reducing the number of points on the convex hull calculation using the polar space subdivision in E2," 2016.

A. N. Gamby and J. Katajainen, "Convex-hull algorithms: Implementation, testing, and experimentation," Algorithms, vol. 11, no. 12, p. 195, 2018.

A. N. Gamby and J. Katajainen, "A faster convex-hull algorithm via bucketing," in International Symposium on Experimental Algorithms, 2019: Springer, pp. 473-489.

K. Borna, "Sweep Line Algorithm for Convex Hull Revisited," Journal of Algorithms and Computation, vol. 51, no. 1, pp. 1-14, 2019.

J. Lesjak, "Pregled in primerjava algoritmov za izračun konveksne ovojnice," 2021.

F. P. Preparata and M. I. Shamos, "Computational Geometry An Introduction," in Computational Geometry: Springer, 1985, pp. 1-35.

J.-R. Sack and J. Urrutia, Handbook of computational geometry. Elsevier, 1999.

M. De Berg, O. Cheong, M. Van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications, Third Edition ed. Springer, 2008.

J. o'Rourke and A. J. Mallinckrodt, "Computational geometry in C," Computers in Physics, vol. 9, no. 1, pp. 55-55, 1995.

W. F. Eddy, "A new convex hull algorithm for planar sets," ACM Transactions on Mathematical Software (TOMS), vol. 3, no. 4, pp. 398-403, 1977.

A. Bykat, "Convex hull of a finite set of points in two dimensions," Information Processing Letters, vol. 7, no. 6, pp. 296-298, 1978.

N. K. Linh, P. T. An, and T. Van Hoai, "A fast and efficient algorithm for determining the connected orthogonal convex hulls," Applied Mathematics and Computation, vol. 429, p. 127183, 2022.

D. M. Steier and A. P. Anderson, Algorithm Synthesis: A comparative study. Springer Science & Business Media, 2012.

D. R. Chand and S. S. Kapur, "An algorithm for convex polytopes," Journal of the ACM (JACM), vol. 17, no. 1, pp. 78-86, 1970.

R. L. Graham, "An efficient algorithm for determining the convex hull of a finite planar set," Info. Pro. Lett., vol. 1, pp. 132-133, 1972.

Downloads

Published

2022-12-31

Issue

Vol. 16 No. 32 (2022)

Section

Artículos

How to Cite

Implementation of algorithms to compute the Convex Hull. (2022). Entre Ciencia E ingeniería, 16(32), 27-34. https://doi.org/10.31908/19098367.2668