Octagonal and hexadecagonal cut algorithms for finding the convex hull of finite sets with linear time complexity

作     者：Hoang, Nam-Dung Linh, Nguyen Kieu Phu, Hoang Xuan 

作者机构：Vietnam Natl Univ VNU Univ Sci Fac Math Mech & Informat 334 Nguyen Trai Hanoi Vietnam Posts & Telecommun Inst Technol Km10 Nguyen Trai Hanoi Vietnam Vietnam Acad Sci & Technol Inst Math 18 Hoang Quoc Viet Rd Hanoi Vietnam 

出 版 物：《APPLIED MATHEMATICS AND COMPUTATION》 (应用数学和计算)

年 卷 期：2024年第481卷

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：International Center of Research and Postgraduate Training in Mathematics Vietnam Academy of Science and Technology, VAST, (NVCC01.02/24-25) Institute of Mathematics, (ICRTM04_2024.03) 

主　　题：Convex hull Linear time algorithm Quickhull algorithm Orienting curves 

摘      要：This paper is devoted to an octagonal cut algorithm and a hexadecagonal cut algorithm for finding the convex hull of n points in R-2, where some octagon and hexadecagon are used for discarding most of the given points interior to these polygons. In this way, the scope of the given problem can be reduced significantly. In particular, the convex hull of n points distributed b(least)-b(most)-boundedly in some rectangle can be determined with the complexity O (n). Computational experiments demonstrate that our algorithms outperform the Quickhull algorithm by a significant factor of up to 47 times when applied to the tested data sets. The speedup compared to the CGAL library is even more pronounced.