Research Progress of Efficient Convex Hull Algorithms

Zhengtao Xiao; Hansheng Yan; Huimin Yi; Juan Zhao; Yongliang Qiu

doi:10.47297/taposatWSP2633-456919.20260707

PDF
导出
分享
收藏
专辑

Research Progress of Efficient Convex Hull Algorithms

7卷第7期

浏览量: 0 Downloads: 0

Research Progress of Efficient Convex Hull Algorithms
Research Progress of Efficient Convex Hull Algorithms
1.School of Electromechanical Engineering, Guangdong Polytechnic of Industry and Commerce, Guangzhou, Guangdong, 510510, China
2.Practical Training Center, Guangdong Polytechnic of Industry and Commerce, Guangzhou, Guangdong, 510510, China
3.Science and Technology Department, Guangdong Polytechnic of Industry and Commerce, Guangzhou, Guangdong, 510510, China
2026年7卷第7期页码：97-100
网络首发：2026-08-21，

纸质出版：2026-07-30
DOI：10.47297/taposatWSP2633-456919.20260707
Accepted：

Scan QR Code

Zhengtao Xiao, Hansheng Yan, Huimin Yi, Juan Zhao & Yongliang Qiu. (2026). Research Progress of Efficient Convex Hull Algorithms. 科技理论与实践（英文版）, 7(7), 97-100.

Xiao Zhengtao,Yan Hansheng,Yi Huimin,et al.Research Progress of Efficient Convex Hull Algorithms[J].Theory and Practice of Science and Technology,2026,07(07):97-100.
Zhengtao Xiao, Hansheng Yan, Huimin Yi, Juan Zhao & Yongliang Qiu. (2026). Research Progress of Efficient Convex Hull Algorithms. 科技理论与实践（英文版）, 7(7), 97-100. DOI： 10.47297/taposatWSP2633-456919.20260707.

Xiao Zhengtao,Yan Hansheng,Yi Huimin,et al.Research Progress of Efficient Convex Hull Algorithms[J].Theory and Practice of Science and Technology,2026,07(07):97-100. DOI： 10.47297/taposatWSP2633-456919.20260707.

摘要

Abstract

The convex hull is among the most fundamental structures in computational geometry and underlies applications in pattern recognition

machine learning

remote sensing

medical imaging

robotics

and operations research. Although the asymptotically optimal complexity of planar convex hull computation has been understood since the 1980s

the period 2020–2026 has seen sustained activity driven by new computing paradigms and new application demands. This paper combines a bibliometric overview with a thematic survey. On the bibliometric side

we draw on the Web of Science Core Collection (396 records

2020–2026) to quantify publication trends and disciplinary breadth

finding that the field is highly interdisciplinary

anchored by electrical and electronic engineering

computer science

and applied mathematics. On the thematic side

we organize recent algorithmic work into five groups: GPU and reconfigurable-hardware implementations; output-sensitive

dynamic

and streaming algorithms; learning-based and quantum approaches; orthogonal and rectilinear convex hulls; and convex-hull membership and vertex-enumeration queries. We then conclude with open problems.

关键词

Keywords

references

Shamos M I. Computational geometry [M]. Yale University, 1978.

Graham R L. An efficient algorithm for determining the convex hull of a finite planar set [J]. Information Processing Letters, 1972, 1: 132-133.

Preparata F P, Hong S J. Convex hulls of finite sets of points in two and three dimensions [J]. Communications of the ACM, 1977, 20(2): 87-93.

Kirkpatrick D G, Seidel R. The ultimate planar convex hull algorithm [J]. SIAM journal on computing, 1986, 15(1): 287-299.

Chan T M. Optimal output-sensitive convex hull algorithms in two and three dimensions [J]. Discrete & Computational Geometry, 1996, 16(4): 361-368.

Carrasco R, Ferrada H, Navarro C A, et al. An evaluation of GPU filters for accelerating the 2D convex hull [J]. J Parallel Distrib Comput, 2024, 184: 10.

Mori T, Manabe T, Shibata Y. A Hardware Oriented Approximate Convex Hull Algorithm and its FPGA Implementation [J]. IEICE Trans Fundam Electron Commun Comput Sci, 2022, E105A(3): 459-467.

Chan T M. Dynamic Geometric Data Structures via Shallow Cuttings [J]. Discrete & Computational Geometry, 2020, 64(4): 1235-1252.

Brewer B, Brodal G S, Wang H T. Dynamic Convex Hulls for Simple Paths [J]. Discrete & Computational Geometry, 2026, 75(4): 1151-1186.

Chan T M, Rahul S. Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points [C]//38th International Symposium on Theoretical Aspects of Computer Science (STACS), Electr Network, 2021.

Liang H J, Wang S H, Gao S, et al. Deephullnet: a deep learning approach for solving the convex hull and concave hull problems with transformer [J]. Int J Digit Earth, 2024, 17(1): 19.

Wang C, Zhou R G. A quantum search algorithm of two-dimensional convex hull [J]. Commun Theor Phys, 2021, 73(11): 8.

Fukuzawa S, Goodrich M, Irani S. Sublinear Work Parallel Quantum Algorithms for Computational Geometry [C]//51st International Conference on Current Trends in Theory and Practice of Computer Science-SOFSEM-Annual, Krakow, POLAND, 2026: 231-245.

Alegría C, Orden D, Seara C, et al. Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations [J]. J Glob Optim, 2021, 79(3): 687-714.

Linh N K. Efficient real-time and parallel algorithm for connected orthogonal convex hulls on large point sets [J]. Numer Algorithms, 2025: 40.

Pérez-Lantero P, Seara C, Urrutia J. Rectilinear convex hull of points in 3D and applications [J]. J Glob Optim, 2024, 90(2): 551-571.

Kalantari B, Zhang Y K. Algorithm 1024: Spherical Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries [J]. ACM Trans Math Softw, 2022, 48(2): 32.

Park K, Schneider M. An in-place Quickhull algorithm [J]. Geoinformatica, 2025, 29(3): 517-545.

Goodrich M T. A lower bound for the Quickhull convex hull algorithm that disproves the Quickhull precision conjecture [J]. Information Processing Letters, 2025, 189: 3.

Ebbens M, Yoshida Y. Average Sensitivity of Geometric Algorithms[C]//17th Conference on Innovations in Theoretical Computer Science-ITCS, Bocconi University, Milan, ITALY, 2026.