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 language | English (US) |
---|---|
Pages (from-to) | 131-142 |
Number of pages | 12 |
Journal | Journal of Interdisciplinary Mathematics |
Volume | 10 |
Issue number | 1 |
DOIs | |
State | Published - 2007 |
Keywords
- Convex hull
- Extreme points
- Linear inequalities
- Probabilistic method
- Redundancy
- Solid angles
ASJC Scopus subject areas
- Analysis
- Applied Mathematics