Optimizing convex hull discovery: Introducing a quintuple-region algorithm with enhanced computational efficiency
This paper introduces a novel algorithm for computing the convex hull of a finite set of points in two-dimensional space. Unlike traditional methods, this algorithm strategically partitions the input set into five distinct regions, isolating interior points to reduce computational efforts while dete...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2025-01-01
|
| Series: | Engineering Science and Technology, an International Journal |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2215098624003045 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850173138728386560 |
|---|---|
| author | Fidan Nuriyeva Hakan Kutucu |
| author_facet | Fidan Nuriyeva Hakan Kutucu |
| author_sort | Fidan Nuriyeva |
| collection | DOAJ |
| description | This paper introduces a novel algorithm for computing the convex hull of a finite set of points in two-dimensional space. Unlike traditional methods, this algorithm strategically partitions the input set into five distinct regions, isolating interior points to reduce computational efforts while determining the convex hulls of the four boundary regions. This innovative approach significantly diminishes the required number of operations, achieving a computational complexity of O(nk), where k denotes the number of vertices on the convex hull and n is the number of vertices. The study methodically elaborates on the development of this algorithm, starting with a comprehensive overview of convex hull related terminology and existing methodologies. Subsequent sections detail the process of identifying endpoints within the set, the division of the set into specific regions, and the application of proposed algorithms for each region to efficiently compute their convex hulls. Through theoretical analysis and case studies presented in the latter sections, this paper not only enhances understanding of convex hull computation but also demonstrates the practical efficiency and effectiveness of the proposed algorithm in various scenarios. This advancement represents a significant contribution to the field of computational geometry, offering improved solutions for problems involving two-dimensional spatial analysis. |
| format | Article |
| id | doaj-art-f08da80eecce4c7abe3da12783ffb2ab |
| institution | OA Journals |
| issn | 2215-0986 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | Engineering Science and Technology, an International Journal |
| spelling | doaj-art-f08da80eecce4c7abe3da12783ffb2ab2025-08-20T02:19:55ZengElsevierEngineering Science and Technology, an International Journal2215-09862025-01-016110191810.1016/j.jestch.2024.101918Optimizing convex hull discovery: Introducing a quintuple-region algorithm with enhanced computational efficiencyFidan Nuriyeva0Hakan Kutucu1Dokuz Eylul University, Faculty of Science, Department of Computer Science, Izmir, Turkiye; Institute of Control Systems, The Ministry of Science and Education of the Republic of Azerbaijan, Baku, Azerbaijan; Corresponding author at: Dokuz Eylul University, Faculty of Science, Department of Computer Science, Izmir, Turkiye.Karabuk University, Department of Software Engineering, Karabük, TurkiyeThis paper introduces a novel algorithm for computing the convex hull of a finite set of points in two-dimensional space. Unlike traditional methods, this algorithm strategically partitions the input set into five distinct regions, isolating interior points to reduce computational efforts while determining the convex hulls of the four boundary regions. This innovative approach significantly diminishes the required number of operations, achieving a computational complexity of O(nk), where k denotes the number of vertices on the convex hull and n is the number of vertices. The study methodically elaborates on the development of this algorithm, starting with a comprehensive overview of convex hull related terminology and existing methodologies. Subsequent sections detail the process of identifying endpoints within the set, the division of the set into specific regions, and the application of proposed algorithms for each region to efficiently compute their convex hulls. Through theoretical analysis and case studies presented in the latter sections, this paper not only enhances understanding of convex hull computation but also demonstrates the practical efficiency and effectiveness of the proposed algorithm in various scenarios. This advancement represents a significant contribution to the field of computational geometry, offering improved solutions for problems involving two-dimensional spatial analysis.http://www.sciencedirect.com/science/article/pii/S2215098624003045Computational geometryConvex hullCircuit coveringAlgorithm |
| spellingShingle | Fidan Nuriyeva Hakan Kutucu Optimizing convex hull discovery: Introducing a quintuple-region algorithm with enhanced computational efficiency Engineering Science and Technology, an International Journal Computational geometry Convex hull Circuit covering Algorithm |
| title | Optimizing convex hull discovery: Introducing a quintuple-region algorithm with enhanced computational efficiency |
| title_full | Optimizing convex hull discovery: Introducing a quintuple-region algorithm with enhanced computational efficiency |
| title_fullStr | Optimizing convex hull discovery: Introducing a quintuple-region algorithm with enhanced computational efficiency |
| title_full_unstemmed | Optimizing convex hull discovery: Introducing a quintuple-region algorithm with enhanced computational efficiency |
| title_short | Optimizing convex hull discovery: Introducing a quintuple-region algorithm with enhanced computational efficiency |
| title_sort | optimizing convex hull discovery introducing a quintuple region algorithm with enhanced computational efficiency |
| topic | Computational geometry Convex hull Circuit covering Algorithm |
| url | http://www.sciencedirect.com/science/article/pii/S2215098624003045 |
| work_keys_str_mv | AT fidannuriyeva optimizingconvexhulldiscoveryintroducingaquintupleregionalgorithmwithenhancedcomputationalefficiency AT hakankutucu optimizingconvexhulldiscoveryintroducingaquintupleregionalgorithmwithenhancedcomputationalefficiency |