Computing the Approximate Convex Hull in High Dimensions

2016/03/08 by Hossein Sartipizadeh, Sartipizadeh, Hossein, Tyrone L. Vincent +1 · 3 citations
Computer Science · Engineering · #52-xx #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Metric Geometry (math.MG) #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1603.04422

openalex publication_date 2016/03/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, an effective method with time complexity of O(K^3/2N²log (K)/(ε₀)) 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.

Cited by

• Probabilistic Robustness Analysis in High Dimensional Space: Application to Semantic Segmentation Network
• A Polynomial-Time Algorithm for Computing the Exact Convex Hull in High-Dimensional Spaces
• On Geometric Structure of Activation Spaces in Neural Networks

Related

• Approximate Convex Hulls: sketching the convex hull using curvature
• A Polynomial-Time Algorithm for Computing the Exact Convex Hull in High-Dimensional Spaces
• Convex hulls of finite sets of points in two and three dimensions
• On the expected diameter, width, and complexity of a stochastic convex-hull
• Finding the vertices of the convex hull, even unordered, takes Omega(n log n) time -- a proof by reduction from epsilon-closeness