Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
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

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.