UM
A fast convex hull algorithm inspired by human visual perception
Liu, Runzong1; Tang, Yuan Yan2; Chan, Patrick P. K.3
2018-12
Source PublicationMULTIMEDIA TOOLS AND APPLICATIONS
ISSN1380-7501
Volume77Issue:23Pages:31221-31237
AbstractThis 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.
KeywordConvex hull Computational geometry Affine transformation Point pattern High dimension
DOI10.1007/s11042-018-6185-0
URLView the original
Indexed BySCI
Language英语
WOS Research AreaComputer Science ; Engineering
WOS SubjectComputer Science, Information Systems ; Computer Science, Software Engineering ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic
WOS IDWOS:000448401600048
PublisherSPRINGER
Fulltext Access
Citation statistics
Cited Times [WOS]:1   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionUniversity of Macau
Affiliation1.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.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Liu, Runzong]'s Articles
[Tang, Yuan Yan]'s Articles
[Chan, Patrick P. K.]'s Articles
Baidu academic
Similar articles in Baidu academic
[Liu, Runzong]'s Articles
[Tang, Yuan Yan]'s Articles
[Chan, Patrick P. K.]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Liu, Runzong]'s Articles
[Tang, Yuan Yan]'s Articles
[Chan, Patrick P. K.]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.