# Representing a point inside a polyhedron as a convex combination of extreme points

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.

-
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

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,

-
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

$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.

-

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.

-