# Computing the Approximate Convex Hull in High Dimensions

arXiv: https://arxiv.org/abs/1603.04422 · HTML: https://mlsanity.com/paper/1603.04422/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2016.

## Built on by (most cited first, 3 of 3)

- [PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximations](https://mlsanity.com/paper/2103.03638/) (2021)
- [Probabilistic Robustness Analysis in High Dimensional Space: Application to Semantic Segmentation Network](https://mlsanity.com/paper/2509.11838/) (2025)
- [Why Robust Natural Language Understanding is a Challenge](https://mlsanity.com/paper/2206.14575/) (2022)

## Abstract (arXiv)

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.