A Characterization Theorem and An Algorithm for A Convex Hull Problem

Original · EN

Given S= {v₁,, vₙ} ⊂ R ᵐ and p ∈ R ᵐ, testing if p ∈ 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' ∈ conv(S) there exists a pivot, vⱼ ∈ S satisfying d(p',vⱼ) ≥ d(p,vⱼ). Equivalently, p ∈ conv(S) if and only if there exists a witness, p' ∈ 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 ε∈ (0,1), an iterate, p' ∈ conv(S), and v ∈ S, if d(p, p') < εd(p,v), it stops. Otherwise, if there exists a pivot vⱼ, it replace v with vⱼ and p' with the projection of p onto the line p'vⱼ. Repeating this process, the algorithm terminates in O(mn {ε⁻², c⁻¹ ε⁻¹ }) arithmetic operations, where c is the visibility factor, a constant satisfying c ≥ ε² and (∠ pp'vⱼ) ≤ 1/√1+c, over all iterates p'. Additionally, (i) we prove a strict distance duality and a related minimax theorem, resulting in more effective pivots; (ii) describe O(mn ε⁻¹)-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.