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

Exercise 1.16 For each polygon in Figure 1.8, find the number of distinct triangulations.


Solution. Not available. Beware, have a feeling that 8abstract algebra and combination mathematics may set in.□

Exercise 1.17 For each n > 3, find a polygon with n vertices that has a unique triangulation.


Solution. The shape quickly came into my mind as it had been haunting me when thinking about the 'ears' problem. How to find something that resembles it, an umbrella, a bat, a boomerang, or a sort of B-2? nothing in real life looks exactly the same as this shape. Precisely put, it is a polygon with two long edges sharing a same vertex at a proper angle with a series of shorter edges connecting the other two ends of the edges, where all these shorter edges are pulled towards the inside, so that except for the vertex and ends thereof, all the other vertices (joining the shorter edges) have interior angles greater than 180 degrees (i.e. concave or reflex). I conjecture that this is the only 'class' of shapes that have the characteristics specified by the question.□

Exercise 1.21 For each n>3, find a polygon with n vertices with exactly two triangulations.


Solution. It can be a shape consisting of two components, being a rectangle attached to one side of the above shape with unique triangulation, where the rectangular component has exactly two triangulations and the 'wing' has unique triangulation.□

Exercise 1.22 For any n ≥ 3, show there is no polygon with n+2 vertices with exactly C_n - 1 triangulations (where C_n is the Catalan number).
Proof. Before starting the proof of this statement, I'd like to mention that proof of the theorem that the number of triangulations of a convex polygon with n+2 vertices is the Catalan number is definitely one of the most beautiful mathematical proofs I have ever seen where I can sense the traces of topology, algebra etc. at the same time, although it's just a very preliminary touch.
As a convex polygon with n+2 vertices has C_n triangulations, a concave one has C_n as well if exterior connections are regarded as diagonals as well. (so triangulation in this sense is merely a pattern of connecting  vertices, or equivalently a way of connecting vertices that can be isomorphically mapped to a corresponding triangulation for the convex counterpart). We now need to exclude pure exterior triangulations from all these connection patterns. Obviously such exterior triangulations can never be one for polygons with number of vertices greater than 4 (shouldn't be very hard to prove), the statement is evident.□