A characterization theorem and an algorithm for a convex hull problem

Research output: Contribution to journalArticle

3 Citations (Scopus)

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 languageEnglish (US)
Pages (from-to)301-349
Number of pages49
JournalAnnals of Operations Research
Volume226
Issue number1
DOIs
StatePublished - Jan 1 2014

Fingerprint

Convex hull
Duality
Factors
Visibility
Simplex method
Approximation
Linear programming
Computational geometry
Minimax
Separation theorem
Geometry
Euclidean distance
Testing

All Science Journal Classification (ASJC) codes

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

Cite this

@article{1ba859ef1ae14f2e879b1a907795be3e,
title = "A characterization theorem and an algorithm for a convex hull problem",
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.",
author = "Bahman Kalantari",
year = "2014",
month = "1",
day = "1",
doi = "10.1007/s10479-014-1707-2",
language = "English (US)",
volume = "226",
pages = "301--349",
journal = "Annals of Operations Research",
issn = "0254-5330",
publisher = "Springer Netherlands",
number = "1",

}

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

In: Annals of Operations Research, Vol. 226, No. 1, 01.01.2014, p. 301-349.

Research output: Contribution to journalArticle

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.

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

VL - 226

SP - 301

EP - 349

JO - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

IS - 1

ER -