Prove or disprove a statement about testing the convexity of a set using the vertices

105 Views Asked by At

Assume we are working in $\mathbb R^d$. Let $A=\text{Conv}(V)$, the convex hull of $V$. Also $B=\text{Conv}(W)$. I am in a situation where I can prove the following: the line segment joining $v$ and $w$ lies in $A\cup B$ for any $v\in V,w\in W$

My intuition suggests the following statement, and if it is true then I can prove that $A\cup B$ is convex.

$\textbf{Statement}$: If the line segment joining $v$ and $w$ lies in $A\cup B$ for any $v\in V,w\in W$, then $A\cup B$ is convex.

Note that if we replace $V,W$ by $A,B$ then it is true. More general, I proved the following as an exercise, which may serve as a partial result.

$\textbf{Lemma}$

If $A_0,...A_n$ are convex, then $$\text{Conv}(A_0\cup ...\cup A_n)=\bigcup_{a_i\in A_i}\text{Conv}(\{a_0,...,a_n\})$$

The above $\textbf{Statement}$ is similar to the special case $n=2$. But the question is, how to test the convexity if we only have information about lines joining $V$ and $W$? For convenience, $V$, $W$ could be thought of as finite sets of vertices.

1

There are 1 best solutions below

0
On BEST ANSWER

Suppose $A\cup B$ is not convex. Then there is a line segment joining some point in $A$ to some point in $B$ which does not lie entirely within $A\cup B$. Take $a$ and $b$ to be the points where said line segment meets the boundaries of $A$ and $B$ respectively. Then we may say that $a$ and $b$ are visible from each other, that is, the line segment $ab$ with endpoints excluded lies entirely outside both $A$ and $B$. This holds if and only if there exists a hyperplane $H$ through $a$ separating $A$ from $b$, and a hyperplane $K$ through $b$ separating $B$ from $a$.

Now $a$ is the convex combination of some vertices in $V$ all of which lie on $H$. At least one of those vertices, call it $v$, must lie on the same side of $K$ as $a$. Therefore, $v\in V$ is also visible from $b$. Applying the same argument to the line segment $vb$, we obtain $w\in W$ which is visible from $v$. Thus the line segment joining $v$ and $w$ does not lie in $A\cup B$, contradicting the assumption.