A characterization theorem and an algorithm for a convex hull problem

Given $$S= \{v_1, \dots , v_n\} \subset {\mathbb {R}}^m$$ S = { v 1 , ⋯ , v n } ⊂ R m and $$p \in {\mathbb {R}}^m$$ p ∈ R m , testing if $$p \in conv(S)$$ p ∈ c o n v ( S ) , the convex hull of $$S$$ 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$$ p lies in $$conv(S)$$ c o n v ( S ) if and only if for each $$p' \in conv(S)$$ p ′ ∈ c o n v ( S ) there exists a pivot, $$v_j \in S$$ v j ∈ S satisfying $$d(p',v_j) \ge d(p,v_j)$$ d ( p ′ , v j ) ≥ d ( p , v j ) . Equivalently, $$p \not \in conv(S)$$ p ∉ c o n v ( S ) if and only if there exists a witness, $$p' \in conv(S)$$ p ′ ∈ c o n v ( S ) whose Voronoi cell relative to $$p$$ p contains $$S$$ S . A witness separates $$p$$ p from $$conv(S)$$ c o n v ( S ) and approximate $$d(p, conv(S))$$ d ( p , c o n v ( S ) ) to within a factor of two. Next, we describe the Triangle Algorithm: given $$\epsilon \in (0,1)$$ ϵ ∈ ( 0 , 1 ) , an iterate, $$p' \in conv(S)$$ p ′ ∈ c o n v ( S ) , and $$v \in S$$ v ∈ S , if $$d(p, p') > \epsilon d(p,v)$$ d ( p , p ′ ) > ϵ d ( p , v ) , it stops. Otherwise, if there exists a pivot $$v_j$$ v j , it replace $$v$$ v with $$v_j$$ v j and $$p'$$ p ′ with the projection of $$p$$ p onto the line $$p'v_j$$ p ′ v j . Repeating this process, the algorithm terminates in $$O(mn \min \{ \epsilon ^{-2}, c^{-1}\ln \epsilon ^{-1} \})$$ O ( m n min { ϵ - 2 , c - 1 ln ϵ - 1 } ) arithmetic operations, where $$c$$ c is the visibility factor, a constant satisfying $$c \ge \epsilon ^2$$ c ≥ ϵ 2 and $$\sin (\angle pp'v_j) \le 1/\sqrt{1+c}$$ sin ( ∠ p p ′ v j ) ≤ 1 / 1 + c , over all iterates $$p'$$ 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})$$ O ( m n ϵ - 2 t ln ϵ - 1 ) , $$t$$ t a natural number, or even $$O(mn \ln \epsilon ^{-1})$$ O ( m n ln ϵ - 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})$$ O ( m n ln ϵ - 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. Copyright Springer Science+Business Media New York 2015