0
$\begingroup$

I know the Caratheodory's theorem states that if a point $x$ lies in the convex hull $Conv(P)$ on a set $P \subset R^{d}$, then $x$ can be written as the convex combination of at most $d + 1$ points in $P$, or more sharply the convex combination of $d + 1$ extremal points in $P$. Here is a short proof.

However, do we have conclusions of how we can pick points $\{ p_{1},\dots, p_{n} \}$ from $P$ such that any $p \in conv(P)$ can be written as a convex combination of points in $\{ p_{1},\dots,p_{n} \}$?

If an explicit way of picking these points is too general of a question, are there any bounds on how many points we need to pick?

Note this is different from Caratheodory's theorem, as we are choosing the points in the first place instead of claiming that any point can be written as convex combination of some points. Similarly, this also applies to the conic hull.

Of course, considering all extremal points would work, but this is too loose of a bound. If I have a hyperectangle in $\mathbb{R}^{n}$, there are total of $2^{n}$ extremal points, but I think we can just pick $n+1$ point such that any points in the conic hull of this rectangle can be written as the conic combinations of these points. This is what I thought, not completely confident that it's true

I know for shapes like a sphere this might be impossible, a more specific question would be to consider a $P$ that only contains finitely many points

$\endgroup$

1 Answer 1

0
$\begingroup$

Let $P$ consist of $n+2$ or more points in $\mathbb R^n$ that are extreme points of a convex set (e.g. any $n+2$ points on a circle). By definition, none is a convex combination of the others. So if you pick any $n+1$ points of $P$, their convex combinations don't include the points you didn't pick.

$\endgroup$
2
  • $\begingroup$ Thank you. But what about conic combinations? $\endgroup$ Commented Oct 17, 2023 at 3:27
  • $\begingroup$ If $n \ge 3$, take a hyperplane that doesn't pass through the origin. A point on that hyperplane is a conic combination of other points on the hyperplane if and only if it is a convex combination of them. $\endgroup$ Commented Oct 17, 2023 at 4:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .