### Abstract

Given (Formula presented.) and (Formula presented.), testing if (Formula presented.), the convex hull of (Formula presented.), 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: (Formula presented.) if and only if for each (Formula presented.) there exists a pivot, (Formula presented.) satisfying (Formula presented.). Equivalently, (Formula presented.) if and only if there exists a witness, (Formula presented.) whose Voronoi cell relative to (Formula presented.) contains (Formula presented.). A witness separates (Formula presented.) from (Formula presented.) and approximate (Formula presented.) to within a factor of two. Next, we describe the Triangle Algorithm: given (Formula presented.), an iterate, (Formula presented.), and (Formula presented.), if (Formula presented.), it stops. Otherwise, if there exists a pivot (Formula presented.), it replace (Formula presented.) with (Formula presented.) and (Formula presented.) with the projection of (Formula presented.) onto the line (Formula presented.). Repeating this process, the algorithm terminates in (Formula presented.) arithmetic operations, where (Formula presented.) is the visibility factor, a constant satisfying (Formula presented.) and (Formula presented.), over all iterates (Formula presented.). In particular, the geometry of the input data may result in efficient complexities such as (Formula presented.), (Formula presented.) a natural number, or even (Formula presented.). Additionally, (i) we prove a strict distance duality and a related minimax theorem, resulting in more effective pivots; (ii) describe (Formula presented.)-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.

Original language | English (US) |
---|---|

Pages (from-to) | 301-349 |

Number of pages | 49 |

Journal | Annals of Operations Research |

Volume | 226 |

Issue number | 1 |

DOIs | |

State | Published - Jan 1 2014 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Decision Sciences(all)
- Management Science and Operations Research

### Keywords

- Approximation algorithms
- Convex hull
- Duality
- Frank–Wolfe algorithm
- Gilbert’s algorithm
- Linear programming
- Minimax

### Cite this

}

*Annals of Operations Research*, vol. 226, no. 1, pp. 301-349. https://doi.org/10.1007/s10479-014-1707-2

**A characterization theorem and an algorithm for a convex hull problem.** / Kalantari, Bahman.

Research output: Contribution to journal › Article

TY - JOUR

T1 - A characterization theorem and an algorithm for a convex hull problem

AU - Kalantari, Bahman

PY - 2014/1/1

Y1 - 2014/1/1

N2 - Given (Formula presented.) and (Formula presented.), testing if (Formula presented.), the convex hull of (Formula presented.), 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: (Formula presented.) if and only if for each (Formula presented.) there exists a pivot, (Formula presented.) satisfying (Formula presented.). Equivalently, (Formula presented.) if and only if there exists a witness, (Formula presented.) whose Voronoi cell relative to (Formula presented.) contains (Formula presented.). A witness separates (Formula presented.) from (Formula presented.) and approximate (Formula presented.) to within a factor of two. Next, we describe the Triangle Algorithm: given (Formula presented.), an iterate, (Formula presented.), and (Formula presented.), if (Formula presented.), it stops. Otherwise, if there exists a pivot (Formula presented.), it replace (Formula presented.) with (Formula presented.) and (Formula presented.) with the projection of (Formula presented.) onto the line (Formula presented.). Repeating this process, the algorithm terminates in (Formula presented.) arithmetic operations, where (Formula presented.) is the visibility factor, a constant satisfying (Formula presented.) and (Formula presented.), over all iterates (Formula presented.). In particular, the geometry of the input data may result in efficient complexities such as (Formula presented.), (Formula presented.) a natural number, or even (Formula presented.). Additionally, (i) we prove a strict distance duality and a related minimax theorem, resulting in more effective pivots; (ii) describe (Formula presented.)-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.

AB - Given (Formula presented.) and (Formula presented.), testing if (Formula presented.), the convex hull of (Formula presented.), 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: (Formula presented.) if and only if for each (Formula presented.) there exists a pivot, (Formula presented.) satisfying (Formula presented.). Equivalently, (Formula presented.) if and only if there exists a witness, (Formula presented.) whose Voronoi cell relative to (Formula presented.) contains (Formula presented.). A witness separates (Formula presented.) from (Formula presented.) and approximate (Formula presented.) to within a factor of two. Next, we describe the Triangle Algorithm: given (Formula presented.), an iterate, (Formula presented.), and (Formula presented.), if (Formula presented.), it stops. Otherwise, if there exists a pivot (Formula presented.), it replace (Formula presented.) with (Formula presented.) and (Formula presented.) with the projection of (Formula presented.) onto the line (Formula presented.). Repeating this process, the algorithm terminates in (Formula presented.) arithmetic operations, where (Formula presented.) is the visibility factor, a constant satisfying (Formula presented.) and (Formula presented.), over all iterates (Formula presented.). In particular, the geometry of the input data may result in efficient complexities such as (Formula presented.), (Formula presented.) a natural number, or even (Formula presented.). Additionally, (i) we prove a strict distance duality and a related minimax theorem, resulting in more effective pivots; (ii) describe (Formula presented.)-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.

KW - Approximation algorithms

KW - Convex hull

KW - Duality

KW - Frank–Wolfe algorithm

KW - Gilbert’s algorithm

KW - Linear programming

KW - Minimax

UR - http://www.scopus.com/inward/record.url?scp=85027928087&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85027928087&partnerID=8YFLogxK

U2 - 10.1007/s10479-014-1707-2

DO - 10.1007/s10479-014-1707-2

M3 - Article

AN - SCOPUS:85027928087

VL - 226

SP - 301

EP - 349

JO - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

IS - 1

ER -