.png){kind=icon}
.png){kind=icon}
Return
A fast convex hull algorithm inspired by human visual perception
.png){kind=icon}
PRE
AI
DOI：10.1007/s11042-018-6185-0.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Convex hull
Computational geometry
Affine transformation
Point pattern
High dimension
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
3
Papers:
1.9W
Citations:
3.2W
Organization
View more organizations