Exercises of Chapter 1 (Part 1/6), Computational Geometry

Lemma 1.3. Every polygon with more than three vertices has a diagonal

Exercise 1.5. Prove that every polygonal region with polygonal holes admits a triangulation of its interior.


Proof. This proof is going to be very sketchy. Lets start with a polygon with one hole, we can use a   approach similar to what was applied to prove Lemma 1.3 to find out two diagonals that both connect two different vertices on the exterior boundary of the polygon and two different vertices on the interior boundary (the boundary of the hole) without crossing any boundaries or vertices. Thus when the polygon surrounded by the two diagonals and the exterior and interior boundaries that connect the vertices on the ends of the diagonals is taken away from the polygon, the polygon becomes one without a hole. Both the remaining polygon and the polygon being taken away can be triangulated according to the previous theorem. The combined triangulation is that for the original polygon. Then using induction, the statement can be generalised to polygons containing any number of holes.□


Exercise 1.10. Prove Corollary 1.9 using induction.

Corollary 1.9. Every Polygon with more than three vertices has at least two ears

Proof. When n=4, the statement is true in that if the quadrilateral is convex it's obvious two ears can be cut out by either of its two diagonals, and if it is concave, the only diagonal marks its two ears. We assume the statement holds for all polygons with fewer than n vertices. Choose a diagonal d joining vertices a and b, cutting P into polygons P₁ and P₂, having n₁  and n₂  vertices respectively.we may have the following cases
1. Both n₁ and n₂ are no less than 4, then each of them has at least one ear doesn't cover the diagonal, so the original polygon they combine to from must have at least two ears.
2. One of them is a triangle, then that triangle is an ear of the original polygon.□

Exercise 1.11. Show that the sum of the interior angles of any polygon with n vertices is π(n-2).

Proof. With the availability of theorem 1.8 which states that every triangulation of a polygon P with n vertices has n-2 triangles, it's not hard to prove. As by definition, all vertices of these triangles are vertices of the polygon, the interior angles of the polygon are composed of the interior angles of all the triangles combined. As every triangle has interior angles the sum of which is π, thus we can see the for the polygon it is π(n-2).□

Exercise 1.12. Using the previous exercise, show that the total turn angle around the boundary of a polygon is 2π. Here the turn angle at a vertex v is π minus the internal angle at v.


Proof. It is pretty easy and trifling to prove this using the previous theorem.□

Exercise 1.13. Three consecutive vertices a, b, c form a mouth of a polygon if ac is an external diagonal of the polygon, a segment wholly outside. Formate and prove about the existence of mouths.

Proof. a minimal instance is a concave quadrilateral.□

Exercise 1.14. Let a polygon P with h holes have n total vertices (including hole vertices). Find a formula for the number of triangles in any triangulation of P.

Some thoughts: This is non-trivial. A good guess is n + 2(h - 1). Now comes the brief proof, suppose a newly added hole has q vertices, causing a sub-polygon of  p vertices to be re-triangulated (it can be proved that the sub-polygon can be made without having a hole), by induction, the  number of triangles for the sub-polygon will change from p - 2 to p+q, the net increase in number of triangles is q+2. Then it's not hard to use induction method to flesh out the proof. □

Exercise 1.15 Let P be a  polygon with vertices (x_i, y_i) in the plane. Prove that the area of P is 
¹/₂ | Σ (x_iy_i-1 - x_i-1y_i)  |


Proof. This is a very important conclusion. Based on the guaranteed existence of triangulation, we can prove this statement by breaking down the area of the polygon into the areas of its forming triangles. □

References
1. Satyan L. Devadoss and Joseph O'Rourke 2011, Discrete and Computational Geometry, Princeton University Press Princeton and Oxford
2. HTML Special Characters, http://brucejohnson.ca/SpecialCharacters.html
3. Writing Fractions in HTML, http://changelog.ca/log/2008/07/01/writing_fractions_in_html