Find a segment inside a polygon

Question

Let $P = A_1 A_2 \dots A_n$ be a polygon in the plane, with $n \geq 4$. That is, it is a closed broken line with no self-intersections. Then $P$ determines an interior and an exterior, by the Jordan curve theorem.

I would like to know if it is always possible to find two vertices $A_i$ and $A_j$ such that the segment $A_i A_j$ is entirely contained in the interior of $P$. (This statement is easy to prove for $n = 4$, just by examining all possible configurations.)

Failing that, is it necessarily possible if I require only that $A_i A_j$ never meet $P$?

Answer 1

Yes:

Every simple polygon has a diagonal, that is, a segment joining two non-consecutive vertices that lies totally inside the polygon.

For a proof, see Chapter 1 of Discrete and Computational Geometry by Devadoss and O'Rourke. This chapter is freely available.

Here is a picture from that chapter that captures the gist of the proof:

See also Diagonals: Feature Column from the AMS by Malkevitch.