Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there some standard way of representing any point in a polyhedron as a convex combination of some of the extreme points ? More precisely, by n poly(n) n extreme points where n is the number of dimensions.

Edit : I am also hoping for an intuitive explanation to any standard formula that exists to achieve the same.

share|improve this question
    
A similar question was asked at MathOverflow, mathoverflow.net/questions/25052/… but it didn't get much response. –  Gerry Myerson Jun 29 '11 at 6:25
    
I think caratheodory's theorem is what i was looking for –  AnkurVijay Jun 29 '11 at 6:36
add comment

3 Answers 3

up vote 1 down vote accepted

I think it's impossible in general. Try with the disk ; all you can get by taking convex combinations of the extreme points is a polygon inscribed inside it, you can never get the whole set. And I think (let's say I... leave this as an exercise =P) that the disk is convex.

In fact, my intuition tells me that this is only possible with polyhedrons ; as soon as you have little curve in there, the curve cannot be "polygonized" with extreme points... and with polyhedrons, well.

If it was clear that you were trying to do that with polyhedrons then perhaps this "n poly(n)" notation was kind of weird.

Since it is easy to deal with convex combinations inside triangles (or n dimensional tetrahedrons, because a basis is easily found) I guess you could try to divide your polyhedron into "sections" by choosing one arbitrary point and letting a straight line link it to all other points. Therefore your convex polyhedron will be divided in triangles (or n-tetrahedrons) in which convex combinations are easily taken with linear algebra.

Hope that helps,

share|improve this answer
    
Oh, I just thought of something : if for each point you were considering you could choose any extreme points, then I guess an algorithm could be constructed as follows : build a convex polyhedron inscribed in your convex set containing your point for which the extreme points touch the frontier of the set, and then apply the tetrahedronization thing I just described. I am pretty sure it would always work but I am not able to give more details right now. –  Patrick Da Silva Jun 29 '11 at 6:42
    
Patrick, In fact my convex set is actually a polyhedron –  AnkurVijay Jun 29 '11 at 6:44
    
I guess the acceptation means that you were okay with the last explanation then. =) –  Patrick Da Silva Jun 29 '11 at 12:44
    
Yes. Thank you very much :) –  AnkurVijay Jun 29 '11 at 13:16
add comment

$n$ isn't enough, e.g., most of the points inside a square can't be written as a convex combination of two of the corners; you need three. There's a theorem that says you need at most $n+1$, I think it's due to Caratheodory. I don't know about its constructive aspects.

share|improve this answer
add comment

You might want to investigate barycentric coordinates (Coxeter: Introduction to Geometry deals with these in the plane, and there are some references online). Canonically these are based on a n-dimensional tetrahedron of reference.

If you take a general polyhedron the representation will not be unique. For two dimensions, consider a square. A general point will be in two of the triangles formed by the vertices, and will have barycentric coordinates representing a convex combination by reference to each.

An n-dimensional tetrahedron has n+1 points.

share|improve this answer
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.