Computing the Approximate Convex Hull in High Dimensions

Abstract

In this paper, an effective method with time complexity of $\mathcal{O}(K^{3/2}{N}^2\log \frac{K}{{\epsilon }_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.

arXiv comment5 pages, 1 figure, The more detailed version will be submitted

Cited by in corpus (7)

• PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximations
• The Phase Stability Network of all Inorganic Materials
• Convex Hulls of Random Walks in Higher Dimensions: A Large Deviation Study
• Semantic Explanations of Predictions
• On Geometric Structure of Activation Spaces in Neural Networks
• Robust estimation of superhedging prices
• The item selection problem for user cold-start recommendation