Randomized Triangle Algorithms for Convex Hull Membership

Abstract

We present randomized versions of the {\it triangle algorithm} introduced in \cite{kal14}. The triangle algorithm tests membership of a distinguished point $p\in {\mathbb{R}}^m$ in the convex hull of a given set $S$ of $n$ points in ${\mathbb{R}}^m$. Given any {\it iterate} $p^{\prime }\in conv(S)$, it searches for a {\it pivot}, a point $v\in S$ so that $d(p^{\prime },v)\ge d(p,v)$. It replaces $p^{\prime }$ with the point on the line segment $p^{\prime }v$ closest to $p$ and repeats this process. If a pivot does not exist, $p^{\prime }$ certifies that $p\notin conv(S)$. Here we propose two random variations of the triangle algorithm that allow relaxed steps so as to take more effective steps possible in subsequent iterations. One is inspired by the {\it chaos game} known to result in the Sierpinski triangle. The incentive is that randomized iterates together with a property of Sierpinski triangle would result in effective pivots. Bounds on their expected complexity coincides with those of the deterministic version derived in \cite{kal14}.

8 pages, 3 figures