Spherical Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries

The it Convex Hull Membership(CHM) problem is: Given a point $p$ and a subset $S$ of $n$ points in $mathbb{R}^m$, is $p in conv(S)$? CHM is not only a fundamental problem in Linear Programming, Computational Geometry, Machine Learning and Statistics, it also serves as a query problem in many applications e.g. Topic Modeling, LP Feasibility, Data Reduction. The {it Triangle Algorithm} (TA) cite{kalantari2015characterization} either computes an approximate solution in the convex hull, or a separating hyperplane. The {it Spherical}-CHM is a CHM, where $p=0$ and each point in $S$ has unit norm. First, we prove the equivalence of exact and approxima