Every polygon with the more than 3 vertices has a diagonal

computational geometrycomputer sciencegeometryproof-explanation

enter image description here
This is an excerpt from the book
Discrete and Computational Geometry"
by Devadoss and O'Rourke.

Lemma 1.3: Every polygon with more than three
vertices has a diagonal.

"Proof: Let v be the lowest vertex of P; if there are several,
let v be the rightmost. Let a and b be the two neighboring vertices
to v. If the segment ab lies in P and does not otherwise touch
the boundary of P, it is a diagonal. Otherwise, since P has more
than three vertices, the closed triangle formed by a, b, and v
contains at least one vertex of P. Let L be a line parallel to
segment ab passing through v. Sweep this line from v parallel
to itself upward toward ab; see Figure 1.4. Let x be the first
vertex in the closed triangle abv, different from a, b, or v,
that L meets along this sweep. The (shaded) triangular region of
the polygon below line L and above v is empty of vertices of P.
Because vx cannot intersect the boundary of P except at v and x,
we see that vx is a diagonal. "

My two questions are:

1) How doe we know there is a vertex
inside the closed triangle we created? I believe it intuitively
but that doesn't help me in a proof.

2) Does the sweeping line exclude this
from being a rigorous proof? And why does the
line sweeping have to be parallel to the triangle
side ab?

Thanks in advance for any help.

Best Answer

  1. If there are no vertices of $P$ in the closed triangle $avb$, then no edge of $P$ intersects the segment $ab$ internally (because for there to be an edge intersecting $ab$ internally, the closed triangle $avb$ must contain a vertex of $P$). Therefore $ab$ is a diagonal (and we are done).

  2. "Sweeping the line" can be rigorously implemented as a function $\phi$ from the closed interval $[0,1]$ to the set of lines parallel to $ab$, where $0$ is mapped to the line through $v$ and $1$ is mapped to the line $ab$. We pick the minimal value of $r$ such that the line $\phi(r)$ passes through a vertex of $P$ other than $v$, and then we pick the vertex (or one of the vertices) that $\phi(r)$ passes through as $x$.

As for why the line has to be parallel to $ab$, it's so that $\phi(1)$ is the line $ab$, and therefore the line sweeps through the entirety of the closed triangle $avb$.

Related Question