3
$\begingroup$

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.

  • 0
    I think caratheodory's theorem is what i was looking for2011-06-29

3 Answers 3

1

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.

1

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

1

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,

  • 0
    Yes. Thank you very much :)2011-06-29