Abstract
The convex hull problem has practical applications in mesh generation, file searching, cluster analysis, collision detection, image processing, statistics, etc. In this paper, we present a novel pruning-based approach for finding the convex hull set for 2D and 3D datasets using parallel algorithms. This approach, which is a combination of pruning, divide and conquer, and parallel computing, is flexible to be employed in a distributed computing environment. We propose the algorithm for both CPU and GPU (CUDA) computation models. The results show that ConcurrentHull has a performance gain as the input data size increases. Providing an independently dividable approach, our algorithm has the benefit of handling huge datasets as opposed to other approaches presented in this paper which failed to manage the same datasets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Robotic 3D Scan Repository (2020). http://kos.informatik.uni-osnabrueck.de/3Dscans/
Barber, C.B., Dobkin, D.P., Huhdanpaa, H.: The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. (TOMS) 22(4), 469–483 (1996)
Blelloch, G.E., Gu, Y., Shun, J., Sun, Y.: Randomized incremental convex hull is highly parallel. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 103–115 (2020)
De Berg, M., Van Kreveld, M., Overmars, M., Schwarzkopf, O.C.: Computational geometry. Computational Geometry, pp. 1–17. Springer, Berlin (2000)
Gao, M., Cao, T.T., Nanjappa, A., Tan, T.S., Huang, Z.: gHull: a GPU algorithm for 3D convex hull. ACM Trans. Math. Softw. (TOMS) 40(1), 1–19 (2013)
Jurkiewicz, T., Danilewski, P.: Efficient quicksort and 2D convex hull for CUDA, and MSIMD as a realistic model of massively parallel computations (2011)
Mei, G.: Cudachain: an alternative algorithm for finding 2D convex hulls on the GPU. SpringerPlus 5(1), 696 (2016)
Miller, R., Stout, Q.F.: Efficient parallel convex hull algorithms. IEEE Trans. Comput. 37(12), 1605–1618 (1988)
o’Rourke, J.: Computational Geometry in C. Cambridge University Press, Cambridge (1998)
Stein, A., Geva, E., El-Sana, J.: Cudahull: fast parallel 3D convex hull on the GPU. Comput. Graph. 36(4), 265–271 (2012)
Tang, M., Zhao, J.Y., Tong, R.F., Manocha, D.: GPU accelerated convex hull computation. Comput. Graph. 36(5), 498–506 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Masnadi, S., LaViola, J.J. (2020). ConcurrentHull: A Fast Parallel Computing Approach to the Convex Hull Problem. In: Bebis, G., et al. Advances in Visual Computing. ISVC 2020. Lecture Notes in Computer Science(), vol 12509. Springer, Cham. https://doi.org/10.1007/978-3-030-64556-4_46
Download citation
DOI: https://doi.org/10.1007/978-3-030-64556-4_46
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-64555-7
Online ISBN: 978-3-030-64556-4
eBook Packages: Computer ScienceComputer Science (R0)