Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm looking for a formal proof of a statement that seems obvious (and yet may be wrong) to make sure one of my algorithms is correct.

Given a set S of N points in $\mathbb{R}^3$, suppose we have a plane such as:

  • two points among the set S belong to that plane
  • all the N points are located on the same side relatively to this plane

Prove that at least one edge of the convex hull of the set S belongs to that plane.

share|improve this question
1  
The hull (with the interior) is convex, so any convex linear combination of those two points has to be contained. If it (the linear combination) is not an edge, then it has to be a face that belongs to that plane and this face has an edge you are looking for. –  dtldarek Jan 30 '13 at 10:51
    
@dtldarek Could you write a more detailed proof? I already know the result is probably true, but I want it to be proven behind any doubt. –  LSA Jan 30 '13 at 13:42
add comment

1 Answer

up vote 1 down vote accepted

Let $H$ be the convex hull, that is, the smallest convex set that includes all the $N$ points of $S$. Set $V$, $E$, $F$, $I$ be the sets of vertices, edges, faces and interior of $H$ respectively, where $V$, $E$, $F$, $I$ are pairwise disjoint that is $H = V \uplus E \uplus F \uplus I$. For example $H = \bar{I}$, that is the closure of $I$, $V = \bar{E}-E$, $V \uplus E = \bar{F}-F$ and $V \uplus E \uplus F = \bar{I}-I$. Furthermore, denote the aforementioned plane as $P$ and let $A,B \in P \cap H$ be the two vertices from the question and $AB$ be the open segment between them.


First, because of convexity, $$H\text{ lies on one side of the plane }P. \tag{1}$$ Let's introduce a Cartesian coordinate system such that $P = \{ p \in \mathbb{R}^3 \mid \pi_z(p) = 0 \}$ and $S \subset \{ p \mid \pi_z(p) \geq 0 \}$. Then $\forall p \in H.\ \pi_z(p) \geq 0$ and thus $H \subset \{p \mid \pi_z(p) \geq 0 \}$.

Also, because of convexity $AB \subset H$ and $AB \subset P$ (plane is convex too).

Consider the following cases:

  1. $AB \cap V \neq \varnothing$. Impossible (please remember that $A,B \notin AB$).

  2. $AB \cap E \neq \varnothing$. In this case we are done (see lemma below).

  3. $AB \cap E = \varnothing$. I will try to show that in this case $AB \cap F \neq \varnothing$ and therefore $F \cap P \neq \varnothing$ which implies the existence of desired edge (the faces are bounded with edges).

We know that $AB \subset F \uplus I$. Let's assume that $AB \cap I \neq \varnothing$. Then, because $I$ is open, for any $p \in AB \cap I$ there exists a small ball with center at $p$ and non-zero radius that is contained in $I$. However, this contradics (1). Then we have $AB \cap I = \varnothing$ and thus $AB \subset F$. Finally $AB \cap F \subset P$, so $E \supset (\bar{F}-F)\cap P \neq \varnothing$. The non-emptiness of the last set implies the existence of the desired edge via the following lemma.


Lemma. Existence of $p \in E \cap P$ implies the existence of an edge $e \ni p$ such that $e \subset P$.

Proof. Let $e$ be any edge such that $p \in e$. Then, because $e$ is open as one dimensional set, there exists a 1D open ball with center at $p$ and non-zero radius, that is contained in $e$. This forces that $e$ is parallel to $P$, but having $p$ as common point, $e \subset P$.


Here are the details, I hope you will enjoy it ;-)

share|improve this answer
    
Thank you very much for taking the time to make such a great answer. –  LSA Jan 31 '13 at 13:57
    
Let's assume that $AB \cap I \neq \varnothing$. Then, because $I$ is open, for any $p \in AB \cap I$ there exists a small ball with center at $p$ and non-zero radius that is contained in $I$. However, this contradics (1). –  LSA Jan 31 '13 at 13:58
    
That's the key argument I did not know how to formalize. –  LSA Jan 31 '13 at 13:58
add comment

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.