Efficient methods for testing if zero lies in a spherical convex shape
Spherical Convex Hull Membership: Complexity and Performance of Geometric and Accelerated Methods
Computational Geometry
Summary
Checking if the center point (origin) is inside a shape formed by many points on a sphere is a tricky problem. The authors study different mathematical methods to solve this problem faster and with fewer steps. They improve existing algorithms by combining ideas and prove how many steps each method might take. They also test these methods on real and synthetic data to see which works best in practice. This helps clarify when certain algorithms are faster or more reliable for these geometric questions.
What this means in practice
- •For machine learning engineers: Improve algorithms that test whether feature vectors contain the zero vector in their convex combinations, aiding classification and optimization tasks.
- •For computer graphics developers: Optimize membership queries in spherical convex shapes for rendering or geometric modeling involving unit vectors.
Authors
Bahman Kalantari
Abstract
We study the problem of testing membership of the origin in the convex hull of $n$ unit vectors in $\mathbb{R}^m$, seeking a convex combination of norm at most $\varepsilon$ or a strict separating hyperplane. The Spherical Triangle Algorithm (STA) uses nearest-point updates on pivot segments. We first establish a conditional $O(1/\varepsilon)$ iteration bound from accumulated geometric progress, allowing deeper pivots to compensate for shallow ones. A three-point example shows that ordinary STA can require $Θ(\varepsilon^{-2})$ 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 $O(\sqrt{\log n}/\varepsilon)$ matrix--vector products with the input matrix or its transpose and $O(mn\sqrt{\log n}/\varepsilon)$ arithmetic operations, including corrections. We also give a self-contained derivation of the $O(\sqrt{\log n}/\varepsilon)$ 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.