I.1 · Foundations — Problem 1 #

← Back to I. Foundations, Problem 1

Problem. (a) Prove that every convex polygon can be triangulated. (b) (Extra credit) Can every polygon be triangulated?

Hint #

(a) Induct on the number of vertices \(n\). The base case \(n=3\) is a triangle. For the inductive step, cut off a single triangle using three consecutive vertices and apply the inductive hypothesis to what remains.

(b) Think about whether you can always find at least one diagonal — a segment between two vertices that stays inside the polygon. If you can, you can always cut the polygon into two smaller ones.

Solution #

Let \(n\) be the number of vertices of the polygon. When \(n=3\), the polygon is a triangle and is already “triangulated.” The proof is by induction, so assume that every convex polygon with \(k\) vertices can be triangulated and consider a convex polygon \(P\) with \(n=k+1\) vertices. Take three consecutive vertices \(v_1\), \(v_2\), and \(v_3\) of \(P\). Since \(P\) is convex, the line segment between \(v_1\) and \(v_3\) lies entirely within \(P\), as does the triangle \(v_1 v_2 v_3\). Removing this triangle from \(P\) leaves another convex polygon \(P'\) with one fewer vertex, and so by our inductive hypothesis, \(P'\) can be triangulated. Together with the triangle \(v_1 v_2 v_3\), we have triangulated \(P\). Hence by induction, any convex polygon can be triangulated.

For (b), rather than a full solution, here is a pointer: the article Triangulation and the Art Gallery Theorem gives a nice exposition, and mentions the “art gallery problem” whose solution was the claim to fame of Bowdoin’s own Steve Fisk. As an aside, computing a triangulation quickly is also interesting: it can be done in linear time, but the algorithm is more-or-less un-implementable.

Long solution #

Strategy. Part (a) is an induction on the number of vertices \(n\). For the inductive step we cut off an ear: the triangle \(T\) spanned by three consecutive vertices \(v_1, v_2, v_3\). What remains should be a convex polygon with one vertex fewer, which the inductive hypothesis triangulates. The short solution says exactly this; the work below is in checking that the ear lies in \(P\), that the remainder is again convex with \(n - 1\) vertices, and that the two pieces overlap only along the cut. Part (b) asks whether convexity can be dropped. It can, but not by cutting ears blindly: at a reflex corner (interior angle bigger than \(180^\circ\)) the ear sticks out of the polygon. Instead we show every polygon has a diagonal, cut along it, and use strong induction.

Definitions. A set is convex if it contains the segment joining any two of its points. A polygon \(P\) is the closed region bounded by a simple closed polygonal curve: finitely many segments (edges) joined end to end, consecutive edges meeting at a shared vertex and non-consecutive edges not meeting at all. A convex polygon is one whose region is a convex set. A triangulation of \(P\) is a finite collection of triangles with disjoint interiors whose union is \(P\). A diagonal is a segment joining two non-adjacent vertices whose interior lies in the interior of \(P\).

We assume no two consecutive edges are collinear, and we use freely the local meaning of “the region bounded by the curve”: near a point inside an edge, \(P\) fills one side of the edge and not the other; near a vertex, the two edges cut a small disk into two sectors, and \(P\) fills exactly one of them (its angle is the interior angle at the vertex).

A fact about convex polygons #

Fact. Let \(P\) be a convex polygon. For each edge \(e\), all of \(P\) lies on one side of the line through \(e\). Consequently, at each vertex \(v\), \(P\) lies in the wedge \(W_v\) spanned by the two edges at \(v\); in particular the interior angle at \(v\) is less than \(180^\circ\), and no vertex is an interior point of a segment contained in \(P\).

Proof. Let \(m\) be the midpoint of \(e\). Near \(m\), one side of the line through \(e\) is outside \(P\). If a point \(p \in P\) lay on that side, the segment \(\overline{pm}\) would lie in \(P\) by convexity, yet its points near \(m\) are on the outside side: a contradiction. For the second statement, the two lines through the edges at \(v\) each have \(P\) on one side; the intersection of those two half-planes is a wedge with apex \(v\), and since it contains the two neighbors of \(v\), it is \(W_v\). A wedge bounded by non-collinear rays opens by less than \(180^\circ\) and so contains no two opposite directions from its apex; a segment through \(v\) inside \(P\) would provide such a pair. \(\square\)

(a) Every convex polygon can be triangulated #

We induct on \(n \geq 3\). A polygon with \(n = 3\) vertices is a triangle and is its own triangulation. Now let \(P\) be convex with \(n \geq 4\) vertices \(v_1, \dots, v_n\) in order around the boundary, and assume the result for convex polygons with \(n - 1\) vertices. Let \(T\) be the triangle \(v_1 v_2 v_3\), let \(\ell\) be the line through \(v_1, v_3\), and let \(H\) be the closed half-plane bounded by \(\ell\) that does not contain \(v_2\).

A convex heptagon with the ear T spanned by v1, v2, v3 shaded orange, the dashed chord line through v1 and v3, dotted lines through the two edges at v2 bounding the wedge W, and the rest of the polygon shaded gray (left); the same triangle and the remaining hexagon v1, v3, …, v7 pulled apart (right).

The inductive step. Left: the ear \(T = v_1 v_2 v_3\), the chord line \(\ell\), and (dotted) the lines through the edges at \(v_2\) bounding the wedge \(W\). Right: the pieces \(T\) and \(P' = P \cap H\) pulled apart; \(P'\) is convex with vertices \(v_1, v_3, \dots, v_n\).

Step 1: the ear lies in \(P\). \(T\) is the smallest convex set containing \(v_1, v_2, v_3\), and \(P\) is a convex set containing them, so \(T \subseteq P\).

Step 2: on the \(v_2\) side of \(\ell\), \(P\) is exactly \(T\). By the Fact, \(P\) lies in the wedge \(W = \{ v_2 + s(v_1 - v_2) + t(v_3 - v_2) : s, t \geq 0\}\). In the coordinates \((s, t)\), the line \(\ell\) is \(s + t = 1\) and \(v_2\) is the origin, so the part of \(W\) on the \(v_2\) side of \(\ell\) is \(\{s, t \geq 0,\ s + t \leq 1\} = T\). Hence every point of \(P\) on the \(v_2\) side of \(\ell\) lies in \(T\), and by Step 1 the converse holds too. Two consequences. First, \(P \cap \ell = \overline{v_1 v_3}\). Second, every vertex other than \(v_2\) lies in \(H\): a vertex \(u \neq v_1, v_2, v_3\) strictly on the \(v_2\) side would lie in \(T\), but a vertex is a boundary point of \(P\), so it is not in the interior of \(T \subseteq P\), and it cannot lie on the sides \(\overline{v_1 v_2}, \overline{v_2 v_3}\), which are edges of \(P\). Moreover no vertex lies in the open chord \((v_1, v_3)\), by the last clause of the Fact.

Step 3: the remainder is a convex polygon with \(n - 1\) vertices. Let \(P' = P \cap H\), a convex set. Since \(v_3, \dots, v_n, v_1 \in H\) and \(H\) is convex, the edges \(\overline{v_3 v_4}, \dots, \overline{v_n v_1}\) lie in \(P'\); the two edges at \(v_2\) meet \(H\) only at \(v_1\) and \(v_3\); and \(P \cap \ell\) is the chord \(\overline{v_1 v_3}\). So the boundary of \(P'\) is the closed polygonal curve \(v_1 \to v_3 \to v_4 \to \cdots \to v_n \to v_1\), which is simple because the chord meets \(\partial P\) only at its endpoints (a point of an edge \(e\) in the open chord would put \(v_1\) and \(v_3\) on opposite sides of the line through \(e\), contradicting the Fact, unless \(e \subseteq \ell\), which is impossible since \(\ell \cap P\) contains no vertices besides the non-adjacent \(v_1, v_3\)). Its corners are genuine: \(v_n, v_1, v_3\) are not collinear, since otherwise \(v_1\) would lie inside a segment of \(P\) or \(v_n\) would lie in the open chord, both excluded. Thus \(P'\) is a convex polygon with the \(n - 1\) vertices \(v_1, v_3, \dots, v_n\).

Step 4: \(P = T \cup P'\), with disjoint interiors. A point of \(P\) is either in \(H\), hence in \(P'\), or strictly on the \(v_2\) side of \(\ell\), hence in \(T\) by Step 2. The interior of \(T\) lies strictly on the \(v_2\) side of \(\ell\), and the interior of \(P' \subseteq H\) lies strictly on the other side.

Step 5: conclusion. By the inductive hypothesis \(P'\) has a triangulation \(\mathcal{T}'\). Its triangles have interiors inside \(\operatorname{int} P'\), which misses \(\operatorname{int} T\), so \(\mathcal{T}' \cup \{T\}\) is a triangulation of \(P' \cup T = P\). By induction, every convex polygon can be triangulated. \(\blacksquare\)

Five panels: a convex heptagon; then the same heptagon with one, two, three, and finally four ears cut off at the vertex v1, ending with a fan of five triangles all sharing the vertex v1.

The induction unrolled: cutting the ear at the same vertex each time produces a “fan” of \(n - 2\) triangles from \(v_1\).

(b) Every polygon can be triangulated #

The answer is yes, but the proof above used convexity twice, in Steps 1 and 2, and both fail at a reflex corner.

Left: a rectangle with a V-shaped notch cut into its top edge; the notch vertex v2 is marked in orange, and the hatched triangle spanned by v1, v2, v3 fills the notch, entirely outside the polygon. Right: the same polygon split by an orange diagonal from v2 to the bottom-left corner into two shaded pieces P1 and P2.

Left: at the reflex vertex \(v_2\) the “ear” \(v_1 v_2 v_3\) lies outside the polygon. Right: a diagonal cuts the polygon into two smaller polygons.

What survives is the idea of cutting along a segment between two vertices, and everything reduces to the following.

Lemma. Every polygon with \(n \geq 4\) vertices has a diagonal.

Two polygons, each with the leftmost vertex v on a dotted vertical line, and its neighbors a and b. Left: the triangle avb contains no other vertex and the segment ab is drawn in orange. Right: two vertices u and w of a notch intrude into the triangle; w is farther from the line ab; a dashed line through w parallel to ab is labeled ell_w, and the segment vw is drawn in orange.

The two cases of the proof. \(v\) is the leftmost vertex, \(a, b\) its neighbors, \(T\) the triangle \(avb\). Left: \(T\) contains no other vertex and \(\overline{ab}\) is a diagonal. Right: \(w\) is the vertex in \(T\) farthest from the line \(ab\), and \(\overline{vw}\) is a diagonal; no vertex lies strictly inside the small triangle \(K\).

Proof. Let \(v\) be a vertex with the smallest \(x\)-coordinate (ties broken by smallest \(y\)-coordinate), with neighbors \(a\) and \(b\), and let \(T\) be the triangle \(avb\).

The corner at \(v\) is convex. Both edges at \(v\) point into the closed right half-plane, and a vertical one points up (by the tie-break), so they span an angle \(\theta < 180^\circ\). Of the two sectors the edges cut from a small disk at \(v\), the larger contains points to the left of \(v\), which \(P\) does not have. So \(P\) fills the smaller sector: near \(v\), the interior of \(P\) is the corner of \(T\).

We use one principle repeatedly: an edge \(e \neq \overline{va}, \overline{vb}\) cannot cross the sides \(\overline{va}, \overline{vb}\) (edges of a simple polygon meet only at shared vertices), so if \(e\) enters a triangle \(Q\) with apex \(v\) and sides along those edges, then following \(e\) in either direction it must either end at a vertex inside \(Q\) or leave through the third side of \(Q\). And a segment cannot leave through the third side in both directions, since it meets that side’s line at most once.

Case 1: no vertex other than \(a, v, b\) lies in \(T\). Then \(a, b\) are not adjacent (else \(P\) is the triangle \(avb\)), and no edge enters \(\operatorname{int} T\) or touches the open segment \((a, b)\): by the principle, such an edge would end at a vertex inside \(T\), which there isn’t, or cross the line \(ab\) twice. So the convex set \(U = \operatorname{int} T \cup (a, b)\) contains no boundary point of \(P\). Pick \(z \in \operatorname{int} T\) near \(v\), an interior point of \(P\). For any \(p \in U\), the segment \(\overline{zp} \subseteq U\) starts inside \(P\) and never meets \(\partial P\), so \(p \in \operatorname{int} P\). Thus \((a, b) \subseteq \operatorname{int} P\): \(\overline{ab}\) is a diagonal.

Case 2: some other vertex lies in \(T\). Let \(w\) be such a vertex farthest from the line \(ab\), let \(\ell_w\) be the line through \(w\) parallel to \(ab\), and let \(K\) be the part of \(T\) on the \(v\) side of \(\ell_w\): a triangle with apex \(v\), sides along the edges at \(v\), and third side on \(\ell_w\). By the choice of \(w\), no vertex other than \(v\) lies in \(K\) off the line \(\ell_w\). The vertices \(v, w\) are not adjacent, the open segment \((v, w)\) lies in \(K\) strictly off \(\ell_w\), and its points near \(v\) are interior to \(P\) since \(w\) is inside the wedge at \(v\). If an edge \(e\) met \((v, w)\), then \(e \neq \overline{va}, \overline{vb}\), and by the principle applied to \(Q = K\), in one of the two directions \(e\) would end at a vertex inside \(K\) off \(\ell_w\), which does not exist. So \((v, w)\) misses \(\partial P\), and as in Case 1 it lies in \(\operatorname{int} P\): \(\overline{vw}\) is a diagonal. \(\square\)

Theorem. Every polygon can be triangulated.

Proof. Strong induction on the number \(n\) of vertices; \(n = 3\) is a triangle. For \(n \geq 4\), the lemma gives a diagonal \(\overline{pq}\), which cuts \(P\) into two polygons \(P_1, P_2\) with disjoint interiors, one on each side of the cut (right panel of the reflex-vertex figure). If \(P_i\) has \(n_i\) vertices then \(n_1 + n_2 = n + 2\), and each \(n_i \geq 3\) because \(p, q\) are non-adjacent; so \(n_i \leq n - 1\). By the inductive hypothesis each \(P_i\) can be triangulated, and the two triangulations together triangulate \(P\). \(\blacksquare\)

A comb-shaped polygon with ten vertices, four spikes along the top and a point on the right, triangulated by seven orange diagonals into eight triangles.

A non-convex polygon with \(n = 10\) vertices, triangulated by cutting along diagonals: \(n - 2 = 8\) triangles and \(n - 3 = 7\) diagonals.

Remark. Any triangulation built this way has exactly \(n - 2\) triangles and \(n - 3\) diagonals: true for a triangle, and if true for the two pieces of a split then the whole has \((n_1 - 2) + (n_2 - 2) = n - 2\) triangles and \((n_1 - 3) + (n_2 - 3) + 1 = n - 3\) diagonals. This count is the first step in Fisk’s three-line proof of the art gallery theorem mentioned in the short solution.