A Characterization Theorem and An Algorithm for A Convex Hull Problem

2012/04/09 by Bahman Kalantari, Kalantari, Bahman · 3 citations
Computer Science · Mathematics · #32C37 #65D18 #90C05 #90C25 #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #F.2.1 #FOS: Computer and information sciences #G.1.6 #I.3.5

paper · pdf · doi:10.48550/arxiv.1204.1873

openalex publication_date 2012/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given S= \v₁, …, v_n\ ⊂ ℝ ^m and p ∈ ℝ ^m, 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 \it 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 \it pivot, v_j ∈ S satisfying d(p',v_j) ≥ d(p,v_j). Equivalently, p \not ∈ conv(S) if and only if there exists a \it 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 \it Triangle Algorithm: given ε∈ (0,1), an \it iterate, p' ∈ conv(S), and v ∈ S, if d(p, p') < ε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 \ε^-2, c^-1ln ε^-1 \) arithmetic operations, where c is the \it visibility factor, a constant satisfying c ≥ ε² and sin (∠ pp'v_j) ≤ 1/√(1+c), over all iterates p'. Additionally, (i) we prove a \it strict distance duality and a related minimax theorem, resulting in more effective pivots; (ii) describe O(mn ln ε^-1)-time algorithms that may compute a witness or a good approximate solution; (iii) prove \it generalized distance duality and describe a corresponding generalized Triangle Algorithm; (iv) prove a \it 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.

Citations

• Smooth minimization of non-smooth functions

Cited by

• The resource theory of causal influence and knowledge of causal influence
• Hyperspectral Image Data Reduction for Endmember Extraction
• Promoting Fairness in Information Access within Social Networks

Related

• An Algorithmic Separating Hyperplane Theorem and Its Applications
• Robust Vertex Enumeration for Convex Hulls in High Dimensions
• Randomized Triangle Algorithms for Convex Hull Membership
• Solving Linear System of Equations Via A Convex Hull Algorithm
• Spherical Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries