A characterization theorem and an algorithm for a convex hull problem
Given \(S= \{v_1, \dots , v_n\} \subset {\mathbb {R}}^m\) and \(p \in {\mathbb {R}}^m\), testing if \(p \in conv(S)\), the convex hull of \(S\), is a fundamental problem in computational geometry and linear programming. First, we prove a Euclidean distance duality, distinct from classical separation theorems such as Farkas Lemma: \(p\) lies in \(conv(S)\) if and only if for each \(p' \in conv(S)\) there exists a pivot, \(v_j \in S\) satisfying \(d(p',v_j) \ge d(p,v_j)\). Equivalently, \(p \not \in conv(S)\) if and only if there exists a witness, \(p' \in conv(S)\) whose Voronoi cell relative to \(p\) contains \(S\). A witness separates \(p\) from \(conv(S)\) and approximate \(d(p, conv(S))\) to within a factor of two. Next, we describe the Triangle Algorithm: given \(\epsilon \in (0,1)\), an iterate, \(p' \in conv(S)\), and \(v \in S\), if \(d(p, p') < \epsilon d(p,v)\), it stops. Otherwise, if there exists a pivot \(v_j\), it replace \(v\) with \(v_j\) and \(p'\) with the projection of \(p\) onto the line \(p'v_j\). Repeating this process, the algorithm terminates in \(O(mn \min \{ \epsilon ^{-2}, c^{-1}\ln \epsilon ^{-1} \})\) arithmetic operations, where \(c\) is the visibility factor, a constant satisfying \(c \ge \epsilon ^2\) and \(\sin (\angle pp'v_j) \le 1/\sqrt{1+c}\), over all iterates \(p'\). In particular, the geometry of the input data may result in efficient complexities such as \(O(mn \root t \of {\epsilon ^{-2}} \ln \epsilon ^{-1})\), \(t\) a natural number, or even \(O(mn \ln \epsilon ^{-1})\). Additionally, (i) we prove a strict distance duality and a related minimax theorem, resulting in more effective pivots; (ii) describe \(O(mn \ln \epsilon ^{-1})\)-time algorithms that may compute a witness or a good approximate solution; (iii) prove generalized distance duality and describe a corresponding generalized Triangle Algorithm; (iv) prove a sensitivity theorem to analyze the complexity of solving LP feasibility via the Triangle Algorithm. The Triangle Algorithm is practical and competitive with the simplex method, sparse greedy approximation and first-order methods. Finally, we discuss future work on applications and generalizations.
convex hull linear programming duality minimax approximation algorithms gilberts algorithm frankwolfe algorithm