Question

Prove that a polygon can be triangulated even if it has holes. Explain your approach with an illustrative example.

Answer 1

A polygon with holes can be triangulated by first tranforming it into a simple polygon
without holes, and then triangulating it. In particular, a hole can be removed by adding
a diagonal from one of the hole vertices to a vertex of the enclosing polygon, e.g., the
diagonal from vertex a to vertex b in the figure. This diagonal can be seen as adding two
additional vertices to the simple polgonal since both sides of the new diagonal represent
external boundaries of the polygon.
This process is repeated for all h holes in the original polygon. The resulting simple polygon
polygon will have n + 2h vertices. Hence, by Theorem 3.1, the triangulated polygon will
have n + 2h − 2 triangles.