pipette
ESEspañol

Spherical Convex Hull Membership: Complexity and Performance of Geometric and Accelerated Methods

Bahman Kalantari

Preprint

In the authors' words

We study the problem of testing membership of the origin in the convex hull of unit vectors in , seeking a convex combination of norm at most or a strict separating hyperplane. The Spherical Triangle Algorithm (STA) uses nearest-point updates on pivot segments. We first establish a conditional iteration bound from accumulated geometric progress, allowing deeper pivots to compensate for shallow ones. A three-point example shows that ordinary STA can require iterations. We show that the same conditional bound holds for STA with Wolfe minimum-norm correction (STA--WMC), provided the averaged geometric progress condition holds for the STA steps taken within this corrected method. We then combine STA, WMC, and the Nemirovski weighted-pivot method (NWP) in a hybrid with unconditional bounds of matrix--vector products with the input matrix or its transpose and arithmetic operations, including corrections. We also give a self-contained derivation of the membership iteration bound for entropic Nesterov acceleration. Computationally, we compare five methods---ordinary STA, STA--WMC, the hybrid, standalone NWP, and entropic Nesterov acceleration---on convex-hull queries derived from 14 public benchmark datasets and on 204 controlled synthetic inputs. STA--WMC completes all cases in both comparisons, and the hybrid completes all public-data cases. STA performs well on favorable interior and separation instances; Nesterov acceleration is faster than the STA-based methods on the highest-dimensional random membership tests. The experiments show complementary strengths and distinguish practical performance from worst-case guarantees.

Main resultLimitation the authors admit

Appeared: Friday, October 16. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 18 pages, 3 tables