0
$\begingroup$

Two questions:

1) (ALREADY ANSWERED) This is likely to be a very basic question for you folks.

Carathéodory's theorem gives us an upper bound for the minimum number of convex hull vertices that can be used in a nonzero convex combination to yield an inner point of the convex hull (d+ 1 in $\mathbb{R}^d$). Is there a result which gives a lower bound on the maximum number of convex hull vertices that can be used in a nonzero convex combination to yield an inner point of the convex hull? (By an inner point I mean one that belongs to the convex hull but does not lie directly on the convex hull.)

I am primarily interested in whether any interior point of a convex hull can always be expressed as a nonzero combination of all convex hull vertices.

ANSWER: Any interior point of a convex hull can be expressed as a nontrivial convex combination of all hull vertices.

2) Would I be correct in saying that the convex hull of any set of points in a simplex is a Choquet simplex, which implies that in this case not only does such a nontrivial convex combination of convex hull vertices exist, but that the convex combination is unique?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

This is indeed easy. Let $p$ be a point that you want to represent, $m$ the barycenter of all vertices and $\varepsilon>0$ so small that the point $q=(1+\varepsilon)p-\varepsilon m=p+\varepsilon(p-m)$ is still in the convex hull. Represent $q$ as a convex combination of some vertices, add $\varepsilon m$ with $m$ represented as the arithmetic mean of all vertices, and finally divide all the coefficients by $1+\varepsilon$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ That settles it! Any interior point of a convex hull can be expressed as a nontrivial convex combination of the hull vertices. $\endgroup$
    – 4fj
    Commented Nov 25, 2012 at 21:07
  • $\begingroup$ Another question: would I be correct in saying that the convex hull of any set of points in a simplex is a Choquet simplex, which implies that in this case not only does such a nontrivial convex combination of convex hull vertices exist, but that the convex combination is unique? $\endgroup$
    – 4fj
    Commented Nov 25, 2012 at 22:25
  • $\begingroup$ Is this still about finite dimensions? If so, a Choquet simplex is just an ordinary simplex, otherwise you need to consider integrals rather than linear combinations. $\endgroup$
    – Sergei Ivanov
    Commented Nov 25, 2012 at 22:30
  • $\begingroup$ Yes, finite dimensions. What I'm trying to ask is: is the convex hull of a set of points in a finite dimensional probability simplex a Choquet simplex? Please excuse my lack of knowledge in these areas... it's funny where research can land you. $\endgroup$
    – 4fj
    Commented Nov 25, 2012 at 22:44
  • $\begingroup$ Answered my own question; it seems that's only the case when the vertices of the convex hull are affinely independent. $\endgroup$
    – 4fj
    Commented Nov 25, 2012 at 23:15
0
$\begingroup$

The following is not a proof (you'll see why in a moment), but is the basis for my belief that there are points which are interior to the convex hull and are nontrivial linear combinations of all the vertices of the convex hull.

Take V, the set all vertices of the convex hull in d dimensions, and do your best to partition into neighboring sets of size d+1. For a simplex in d dimensions, some version of barycentric coordinates should make it clear that each neighboring set has a realm of points interior to the hull which contains a simplex worth of points that are nontrivial combinations of each set. The effect of the partition is to replace the problem of size V with one of size roughly V/d: pick one point which is a representative combination of each neighboring set, and form V', while reusing any vertices from V that were left out of the initial partition. You should be able to work your way down to at most 2d interior vertices, and you might even arrange the result to be convex at each step.

This is not a proof because I am not guaranteeing convexity, nor that when you get down to at most 2d vertices that things will work out. In my geometric worldview however, I can imagine lopping off d vertices at a time in a controlled fashion to converge to a particular interior point, so the picture above might be useful in showing which (if not all) interior points are nontrivial combinations of all the vertices.

Gerhard "One Simplex At A Time" Paseman, 2012.11.25

Improve this answer
$\endgroup$
1
  • $\begingroup$ Actually, the 2d case might work out if you shift your perspective: replace a facet with k vertices by a certain combination that lies on the facet. You could even start with that to reduce V to the right number of vertices mod d (the integer). Gerhard "Ask Me About System Design" Paseman, 2012.11.25 $\endgroup$
    – Gerhard Paseman
    Commented Nov 25, 2012 at 20:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .