Finding the convex combination of vertices which yields an inner point of a polytope - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T08:30:06Z http://mathoverflow.net/feeds/question/88457 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/88457/finding-the-convex-combination-of-vertices-which-yields-an-inner-point-of-a-polyt Finding the convex combination of vertices which yields an inner point of a polytope Guy Adini 2012-02-14T20:51:31Z 2012-02-15T08:19:32Z <p>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.</p> <p>I am interested in figuring out the computational complexity (and algorithm, if available) of finding such a set.</p> <p>Thanks!</p> http://mathoverflow.net/questions/88457/finding-the-convex-combination-of-vertices-which-yields-an-inner-point-of-a-polyt/88485#88485 Answer by Gerhard Paseman for Finding the convex combination of vertices which yields an inner point of a polytope Gerhard Paseman 2012-02-15T04:29:38Z 2012-02-15T04:29:38Z <p>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.</p> <p>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.</p> <p>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.</p> <p>Gerhard "Ask Me About System Design" Paseman, 2012.02.14</p> http://mathoverflow.net/questions/88457/finding-the-convex-combination-of-vertices-which-yields-an-inner-point-of-a-polyt/88498#88498 Answer by Aaron Meyerowitz for Finding the convex combination of vertices which yields an inner point of a polytope Aaron Meyerowitz 2012-02-15T08:19:32Z 2012-02-15T08:19:32Z <p>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 <a href="http://en.wikipedia.org/wiki/Carath%C3%A9odory%27s_theorem_%28convex_hull%29#Proof" rel="nofollow">standard proof</a>s 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.</p> <p>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. </p>