Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

I'm looking for the extreme points of the convex set $S\subset [-1,1]^{n\times 3}$ with $r\in S$ such that \begin{equation} r_{i} \ge r_{k} \iff i\ge k, \end{equation} where the first inequality refers to lexicographical inequality in $\mathbb{R}^3$, and \begin{equation} \sum_i^n r_i = 0 \end{equation} It was easy to characterize the extreme points satisfying only the first set of constraints. The second set has proven to be more difficult and I don't want to waste my time when there's already a solution out there.

Are there any program packages or methods out there that would easily solve this problem? If so, what are they?

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

The most reputable-looking source I could find was

M. E. Dyer, L. G. Proll. An algorithm for determining all extreme points of a convex polytope, Mathematical Programming, Vol. 12, Issue 1, p. 81-96.

The problem is likely only solvable for the case of convex polyhedra; there is a theorem that states that convex polyhedra can be expressed in terms of a convex combination of a finite number of extreme points and a finite number of extreme rays. No such claim can be made about convex sets in general.

The algorithm runtime will be exponential in the dimensionality of the polyhedron. To enumerate all of the vertices of an $n$-cube, all $2^n$ vertices must be enumerated. The problem is probably NP-hard.

share|improve this answer
    
I was afraid of that. I had various versions; some more efficient than others. The big jump is going from three to four points. I don't have access to that article right now, but the abstract suggests it contains what I need (and that I may have had the right general idea). –  Deathbreath Jan 4 '13 at 21:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.