Edges of the convex hull of a finite point set

Question

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.

Answer 1

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