# Edges of the convex hull of a finite point set

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.

-
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

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 ;-)

-
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