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
全文获取链接
引用统计
Document TypeJournal article
专题University 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
推荐引用方式
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.
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
Google Scholar
中相似的文章 Google Scholar
[Liu, Runzong]的文章
[Tang, Yuan Yan]的文章
[Chan, Patrick P. K.]的文章
Baidu academic
中相似的文章 Baidu academic
[Liu, Runzong]的文章
[Tang, Yuan Yan]的文章
[Chan, Patrick P. K.]的文章
Bing Scholar
中相似的文章 Bing Scholar
[Liu, Runzong]的文章
[Tang, Yuan Yan]的文章
[Chan, Patrick P. K.]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。