Finding the convex combination of vertices which yields an inner point of a polytope Given a convex polytope $P\in \mathbb{R}^n$, and a point $x\in P$, Caratheodory's theorem gives us that there exists a set of at most $n+1$ vertices of $P$, such that $x$ is a convex combination of the elements of this set.
I am interested in figuring out the computational complexity (and algorithm, if available) of finding such a set.
Thanks!
 A: Hopefully I am using the right notion of convex combination.  The following requires at most n+1 steps, however I do not know how complicated a step is.
Take the given point x and a vertex v visible from x.  Thus the line through v and x passes through the polygon from v to x to a point p on a face or facet on the other side. x should be a convex combination of v and p.  But p is a point interior to a polygon of smaller dimension, and (if I haven't missed my guess) is a convex combination of n or fewer vertices of the polytope. Now induct with p taking the role of x.
I can imagine having to search the vertex space to find v at each stage.  However, coming up with a simplicial decomposition of certain parts of the polytope may speed up this part.
Gerhard "Ask Me About System Design" Paseman,  2012.02.14
A: It may depend on how the point is given to you and what various operations cost you. If we assume that $x$ is given to you as a convex combination $x=\sum_1^N\lambda_ix_i$ with the $\lambda_i$ positive and adding to $1$ then one of the standard proofs of the theorem reduces $N$ to $N-1$ and starts by finding a linear dependence among the quantities $x_j-x_i$ for $2 \le j \le N$ (unless $N \le n+1$ in which case you are done.) So this would entail solving systems of linear equations several times although not doing linear programming. If $N$ is only a bit larger than $n+1$ this might be reasonable.
Here is a rough idea for for $N$ much larger than $n+1$ and illustrated for $n=3$ which seems like it should work in general. The idea is to cut down the $x_i$ into a subset of about half the size which still contains $P$ in its convex hull.   Pick $n-1(=2)$ of the given points determining a flat $L$ of dimension $n-2$ (a line). Then the flats of dimension $n-1$ (planes) on $L$ give a linear order to the remaining $N-n+1$ points and $x$:  Pick a line $\ell$ on $x$ and let $y_i \in \ell$ be the point of intersection with the flat (plane) $E_i$ determined by $L$ and $x_i \notin L$. Now $x$ will fall between two of the $y_i$, say $y_1$ and $y_2$. Each of the flats $E_1$ and $E_2$ split $R^n$ into half spaces. Choose the plane which puts $x$ into a half space $H$ with no more than half of the $y_i.$ Then $H \cap P$ is a polytope with at most $\frac{N+n+1}2$ vertices which contains $x$ in its convex hull.
