Residential College | false |
Status | 已發表Published |
A fast convex hull algorithm inspired by human visual perception | |
Liu, Runzong1; Tang, Yuan Yan2; Chan, Patrick P. K.3 | |
2018-12 | |
Source Publication | MULTIMEDIA TOOLS AND APPLICATIONS
![]() |
ISSN | 1380-7501 |
Volume | 77Issue:23Pages:31221-31237 |
Abstract | This paper proposes a convex hull algorithm for high dimensional point set, which is faster than the well-known Quickhull algorithm in many cases. The main idea of the proposed algorithm is to exclude inner points by early detection of global topological properties. The algorithm firstly computes an initial convex hull of 2*d + 2(d) extreme points. Then, it discards all the inner points which are inside the inscribed ball of the initial convex hull. The other inner points are processed recursively according to the relationships of points and facets. Maximum inscribed circle affine transformations are also designed to accelerate the computation of the convex hull. Experimental results show that the proposed algorithm achieves a significant saving of computation time in comparison with the Quickhull algorithm in 3, 4 and 5 dimensional space. The space efficiency of the proposed algorithm is also demonstrated by experimental results. |
Keyword | Convex Hull Computational Geometry Affine Transformation Point Pattern High Dimension |
DOI | 10.1007/s11042-018-6185-0 |
URL | View the original |
Indexed By | SCIE |
Language | 英語English |
WOS Research Area | Computer Science ; Engineering |
WOS Subject | Computer Science, Information Systems ; Computer Science, Software Engineering ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic |
WOS ID | WOS:000448401600048 |
Publisher | SPRINGER |
Scopus ID | 2-s2.0-85048042705 |
Fulltext Access | |
Citation statistics | |
Document Type | Journal article |
Collection | University of Macau |
Affiliation | 1.Chongqing Univ, Coll Comp Sci, Chongqing 400030, Peoples R China; 2.Univ Macau, Fac Sci & Technol, Macau, Peoples R China; 3.South China Univ Technol, Guangzhou, Guangdong, Peoples R China |
Recommended Citation GB/T 7714 | Liu, Runzong,Tang, Yuan Yan,Chan, Patrick P. K.. A fast convex hull algorithm inspired by human visual perception[J]. MULTIMEDIA TOOLS AND APPLICATIONS, 2018, 77(23), 31221-31237. |
APA | Liu, Runzong., Tang, Yuan Yan., & Chan, Patrick P. K. (2018). A fast convex hull algorithm inspired by human visual perception. MULTIMEDIA TOOLS AND APPLICATIONS, 77(23), 31221-31237. |
MLA | Liu, Runzong,et al."A fast convex hull algorithm inspired by human visual perception".MULTIMEDIA TOOLS AND APPLICATIONS 77.23(2018):31221-31237. |
Files in This Item: | There are no files associated with this item. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment