A Polynomial-Time Algorithm for Computing the Exact Convex Hull in High-Dimensional Spaces

This study presents a novel algorithm for computing the convex hull of a point set in high-dimensional Euclidean space. The proposed method iteratively solves a sequence of dynamically updated quadratic programming (QP) problems for each point and exploits their solutions to establish theoretical guarantees for exact convex hull identification. For a dataset of \( n \) points in an \( m \)-dimensional space, the algorithm attains a dimension-independent worst-case time complexity of \( O(n^{p+2}) \), where \( p \) depends on the choice of QP solver (e.g., \( p = 4 \) corresponds to the worst-case bound using an interior-point method). The approach is particularly effective for large-scale, high-dimensional datasets, where existing exponential-time algorithms are computationally impractical.