Probabilistic algorithms for extreme point identification

Shafiu Jibrin, Arnon Boneh, Richard J. Caron

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

For a finite set of distinct points S = {pi ε l} in ℝd there exists Î ⊆ I such that all points in Ŝ = {pi i ε Î} are extreme points and conv(Ŝ) = conv(S). Since a point pk ε S is extreme if and only if the inequality pTk y ≤ 1 is necessary with respect to the representation {y ε ℝd{pipe} pTi y≤ 1, i ε I} of the polar dual SΔ of S, Ŝ can be found by classifying the inequalities in the representation as necessary or redundant. Thus, the problem of finding Ŝ is polynomial. This paper shows the advantage of using probabilistic hit-and-run algorithms applied to the polar dual for the quick identification of points in Ŝ and shows how, in an application to a certain cluster analysis problem, it can be used to also identify points in S/Ŝ. Further, it shows that the hit-and-run variant known as Stand-and-Hit provides approximations for the exterior solid angles at the extreme points of S.

Original languageEnglish (US)
Pages (from-to)131-142
Number of pages12
JournalJournal of Interdisciplinary Mathematics
Volume10
Issue number1
DOIs
StatePublished - 2007

Keywords

  • Convex hull
  • Extreme points
  • Linear inequalities
  • Probabilistic method
  • Redundancy
  • Solid angles

ASJC Scopus subject areas

  • Analysis
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Probabilistic algorithms for extreme point identification'. Together they form a unique fingerprint.

Cite this