Computing the Approximate Convex Hull in High Dimensions

In this paper, an effective method with time complexity of O(K3/2N2log fracKε0) is introduced to find an approximation of the convex hull for N points in dimension n, where K is close to the number of vertices of the approximation. Since the time complexity is independent of dimension, this method is highly suitable for the data in high dimensions. Utilizing a greedy approach, the proposed method attempts to find the best approximate convex hull for a given number of vertices. The approximate convex hull can be a helpful substitute for the exact convex hull for on-line processes and applications that have a favorable trade off between accuracy and parsimony.