# 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.) –  Joseph O'Rourke Feb 14 '12 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. –  Suvrit Feb 15 '12 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? –  JeffE Feb 15 '12 at 10:19
Just wondering, are you interested in algorithms that preprocess P to use it for many x? –  Zsbán Ambrus Feb 15 '12 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.

-
The polytope being convex, every vertex is visible from every point of it. –  Gerry Myerson Feb 15 '12 at 4:46
Indeed. I am hoping that this will generalize to nonconvex polytopes. Gerhard "Ask Me About System Design" Paseman, 2012.02.14 –  Gerhard Paseman Feb 15 '12 at 4:55
Very nice argument! –  Joseph O'Rourke Feb 15 '12 at 12:20
As you say, it might be a (much) harder problem to answer: "given P and a line intersecting it at v (a vertex), find the subset of the the vertices of P which determines a facet containing the other intersection point" –  Aaron Meyerowitz Feb 15 '12 at 12:58

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.

-
Usually "given a point" means "given the Cartesian coordinates of a point". –  JeffE Feb 15 '12 at 10:20
"Given x in P" might reasonably be taken to mean that we have a linear combination proving that membership (which would also give the coordinates of x). If the problem was "Given a set V of points and an extra point x , decide if x is in P, the convex hull of V, and if so find a subset of n+1 points..." then we might just have the coordinates. –  Aaron Meyerowitz Feb 15 '12 at 12:51