Every polygon with the more than 3 vertices has a diagonal

Question

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.

Answer 1

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$.