discrete math Mathematical Induction in Computer Graphics Re

discrete math

Mathematical Induction in Computer Graphics Read the proof of the following theorem from your textbook and write the proof in your own words A simple polygon with n sides, where n is an integer with n 2 3, can be triangulated into n 2 triangles

Solution

Any polygon of nvertices can be triangulated.

Base Case:n= 3 is trivial.

Inductive Hypothesis: Any polygon with less than n vertices can be triangulated.

Induction Case: Given our n-gon, P, there exists an internal diagonal AB that splits the polygon into two polygons,Q and R. If Q has k vertices, then R has (n–k+2) vertices, since we reuse A and B. But our inductive hypothesis says that Q can be triangulated into (k-2) triangles and R into (n-k) triangles. Since P is the disjoint union of Q and R (except for boundaries), P will be the union of all the triangles of Q and R, which don\'t intersect. So there will be:

                                               (k–2) + (n–k) = (n-2) triangles, all together,

and the induction holds.Therefore, any polygon P of n vertices can be triangulated into (n-2) triangles.