6
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ 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.) $\endgroup$ Feb 14, 2012 at 21:56
  • $\begingroup$ 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. $\endgroup$
    – Suvrit
    Feb 15, 2012 at 1:25
  • $\begingroup$ 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? $\endgroup$
    – JeffE
    Feb 15, 2012 at 10:19
  • $\begingroup$ Just wondering, are you interested in algorithms that preprocess P to use it for many x? $\endgroup$ Feb 15, 2012 at 10:31

2 Answers 2

6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ The polytope being convex, every vertex is visible from every point of it. $\endgroup$ Feb 15, 2012 at 4:46
  • $\begingroup$ Indeed. I am hoping that this will generalize to nonconvex polytopes. Gerhard "Ask Me About System Design" Paseman, 2012.02.14 $\endgroup$ Feb 15, 2012 at 4:55
  • $\begingroup$ Very nice argument! $\endgroup$ Feb 15, 2012 at 12:20
  • $\begingroup$ 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" $\endgroup$ Feb 15, 2012 at 12:58
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Usually "given a point" means "given the Cartesian coordinates of a point". $\endgroup$
    – JeffE
    Feb 15, 2012 at 10:20
  • $\begingroup$ "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. $\endgroup$ Feb 15, 2012 at 12:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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