# 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!

• I think you could find the including set in time proportional to the number of vertices of $P$ times an LP cost, which is unlikely to be adequate for your (or anyone's!) purposes. Start with $P$, and eliminate redundant vertices one-by-one. I think each elimination could be done by LP. (A polynomial-time algorithm for finding a Tverberg partition [related problem] is an open problem.) Feb 14, 2012 at 21:56
• This sounds like a classic question, but I don't know an answer offhand. However, a simple greedy approach might work: pick a random sample of $n+1$ vertices, see if that works, if not, add more. (Of course this approach is suboptimal), but I guess could be made rigorous. Feb 15, 2012 at 1:25
• Exactly how are you "given" the polytope?! As a finite set of points (whose convex hull is the polytope), as a finite set of halfspaces (whose intersection is the polytope), or something else? Feb 15, 2012 at 10:19
• Just wondering, are you interested in algorithms that preprocess P to use it for many x? Feb 15, 2012 at 10:31

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.

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.