A Convexity Problem

Ali.Kh · P versus NP Offline Joined: 18 Dec 2004 Posts: 30

Given a shape $X \subset \mathbb{R}^n$ prove that if $X$ is connected then the convex hull of $X$ is the union of convex hulls of its subsets with size $n$
$\displaystyle \\conv(X)=\bigcup \{{\sum_{i=1}^n{\lambda_ix_i} \mid \lambda_i\geq 0 , \sum{\lambda_i}=1,x_i\in X}}\}$

grobber

Wow! Cool! Smile

It's a generalization of this one, where we had $n=2$ .

**Posted:** Sun Jan 23, 2005 5:04 am

Omid Hatami

This is something stronger than Caratheodory theorem for connected sets.
Me and Ali proved this 5 days ago

**Posted:** Sun Jan 23, 2005 8:03 am

_________________
No pain, no gain

Omid Hatami

And also Caratheodory theorem is that:
$\displaystyle \\conv(X)=\cup {\sum_{i=1}^{n+1}{\lambda_ix_i}$ such that $\lambda_i\geq 0$ and $\sum{\lambda_i}=1,x_i\in X}}$

**Posted:** Sun Jan 23, 2005 8:07 am

_________________
No pain, no gain

Ali.Kh · P versus NP Offline Joined: 18 Dec 2004 Posts: 30

Hint:
We prove it for $n=2$
if $P \in conv(X)$ then by Caratheodory theorem is in the convex hull of three points of X.so there is $A,B,C\in X$ so that P is in triangle $ABC$ .If P is on one of the sides then the assertion is true(we want to prove that $P$ is between two points of $X$ ).If not, Then a connected path between $A,B$ cuts one of halflines showed below.If this path cuts for example half line $L$ at $M$ then $P\in AM$ .

**Posted:** Sun Jan 30, 2005 10:16 pm

_________________
Dripping water wears a stone...

grobber

I think I proved it for $n=2$ in that thread I mentioned in my first mssage on this topic. Besides, I think you considered your set to be path connected, while the problem asks to prove it for connected sets. Please don't post any more hints, because I don't think people like solving problems after being given copious hints... Smile

**Posted:** Mon Jan 31, 2005 2:47 am

Myth

Can anybody definitely say what kind of connectivity we should use?

**Posted:** Mon Jan 31, 2005 12:43 pm

_________________
Myth is out of here

grobber

I think it's connectedness (i.e. we don't need path connectedness). I can visualize it in three dimensions and I think I can solve it in the general case, but I don't know if I can explain it properly.

I'll solve it for $n=3$ , and I'm sure it will be obvious what to do for higher dimensions.

By Caratheodory (I didn't know this theorem when I solved the problem in the other thread, for $n=2$ Smile

), we know that the point we're working with, $P$ , lies in a tetrahedron $ABCD$ with $A,B,C,D\in\mathcal X$ . We may assume $P$ is strictly inside this tetrahedron and does not belong to $\mathcal X$ , otherwise we're done. Consider now the (open) region $\mathcal R$ of space bounded by the plane angles $\angle B'PC',\angle C'PD',\angle D'PB'$ , where $B',C',D'$ are on $(BP,(CP,(DP$ respectively ( $B,B'$ are on opposite sides of $P$ , adn the same holds for $C,C'$ and $D,D'$ ).

If none of these angles contains a point from $\mathcal X$ , the partition $\mathcal X=(\mathcal X\cap\mathcal R)\cup (\mathcal X\setminus \mathcal R)$ shows that $\mathcal X$ is not connected, because both $\mathcal X \cap \mathcal R$ and $\mathcal X\setminus\mathcal R$ are non-void, the first one containing $A$ , and the second one containing $B,C,D$ , for example.
Think it's Ok? It seems too short.. Confused

**Posted:** Mon Jan 31, 2005 3:05 pm