Exercises of Chapter 3 (Part 1/5), Computational Geometry

Exercise 3.2 Show that the edges of the convex hull of a point set S will always be in every triangulation of S.

Proof. Because they are not crossing any of the edges other than themselves that have two points of S as its end points. □


Exercise 3.3 The definition of a triangulation of a point set does not even mention "triangles". Show that all the regions of subdivision inside the convex hull must indeed be triangles


Proof. The definition is repeated here again
A triangulation of a planar point set S is a subdivision of the plane determined by a maximal set of non-crossing edges whose vertex set is S.
As they  are non-crossing each regions of subdivision must be a polygon. However if it's a polygon with more than 3 vertices, it can be further divided thus the set has yet to reach maximum.□


Exercise 3.4 Extend the triangle-splitting algorithm to work for points that may include three or more collinear points (but not all collinear)

Solution. Find the convex hull first leaving all the points on the edges of the hull between vertices out. Triangulate the hull ignoring again all the points on the edges. Performing the proceedings of the original algorithm for all points strictly interior to existing triangles with again points on edges ignored. Finally triangulate all the triangles just triangulated with points on edges.□


Exercise 3.5 Analyse the time complexity of the triangle-splitting algorithm.


Analysis. Only the original algorithm for non-collinear point set is considered. Hull finding takes O(n log n). Suppose there are m points on the hull, then there are m-2 triangles created by the initial triangulation, and m-n points inside.  Each point to be added needs to be checked against all existing triangles and adds two triangles to the triangulation once added. The check determines if the point is inside the particular triangle, which take constant time. So this phase has  (m+n-5)(n-m)/2 steps which is basically O(n²). Therefore the overall complexity is O(n²). □

Exercise 3.7 Prove or disprove: The triangle-splitting algorithm produces all possible triangulations of a point set.


Disprove (It's not true). As the triangulation produced by this algorithm has the restriction that it must contain diagonals of the hull, a counter-example can easily made by a triangulation of point set which doesn't contain any diagonals of the hull. □

Exercise 3.8 Analyse the complexity of the incremental algorithm.


Analysis. Sorting takes O(n log n); Visibility testing for about n nodes requires O(n²) time at minimum (by keeping track of the hull and performing the same process as for convex hull finding). So the overall complexity is O(n²). □

Exercise 3.9 Prove that the incremental algorithm produces a triangulation of a point set in general position.


Prove. Just discuss a special case where three points are collinear and the point behind is not considered as it's not visible to the current point, which is fine as it's the right way to do the triangulation. □

Exercise 3.10 Prove or disprove: The incremental algorithm produces all possible triangulations of a point set in general position.


Disprove (It's not true). Imagine a big triangle with quite a few points near all of its three edges exterior to the triangle, when properly set this point set can never be triangulated in such a way that the edges of big triangle remain. □

Exercise 3.11 Alter the Graham scan convex hull algorithm (Section 2.4) to compute triangulations.


Solution. Each time a new vertex is being processed, it should be combined with the latest edge scanned through to form a new triangle. For each reflex point (with right turn) encountered in the scanning process, simply add the triangle formed by the point and the edge introduced to eliminate the right turn. □


Exercise 3.14 Show that every triangulation has some vertex of degree at most five.


Proof. Use theorem 3.13 which declares that any triangulation of point set with n = k + h points where k is the the number of  interior vertices and h that of those on the hull has 3k + 2h - 3 edges. Those edges are shared by those vertices. So the summed degree of the vertices is twice the edge number, which is 6k + 4h - 3, distributed to n vertices. According to pigeon hole principle at least one vertex has degree no more than ⌊( 6k + 4h - 3 ) / (k + h)⌋ = ⌊6 - ( 2h + 3 ) / (k + h)⌋  ≤  5. □


Exercise 3.15 Construct a point set S with n+2 points such that the number of triangulations of S is greater than Catalan number C_n.


Example. See the example in Exercise 3.18 when n gets to 6. □

Exercise 3.17 Compare this value (30ⁿ, which is the upper bound of number of triangulations of an arbitrary point set) with Catalan number derived in Theorem 1.19.

Analysis. Number of triangulations of convex hull with n vertices is C_n-2, this number is generally smaller and growing (at a rate lower than 4) much slower than 30ⁿ. □

Exercise 3.18 Consider the point set S given in Figure 3.5. It is made of two "double chains" of points, where every pair of points from different chains is visible to each other. Show that the edges drawn in the figure appear in every triangulation of S. Moreover, if there are n points in each chain, find the number of triangulations of S.


Proof. If two points are not connected in a triangulation there must be an edge in the triangulation going across the edge that connects the two points. As every pair of points from different chains is visible to each other, it can be proved that there is no such edge for all the edges drawn in the figure.
Solution to the question. If we use T(m,n) to denote the number of triangulations between the chains of a point set which takes m points from the upper chain and n from the lower chain (it can be proved that this measurement is always applicable to this point set and any of its subsets). It is easy to see the following relationships
T(m,n) = T(n,m)
T(m,n) = T(m-1,n) + T(m,n-1)
T(m,1) = 1
The above relationships lead to T(m,n) = C(m+n-2, m-1) and T(n,n) = C(2n-2, n-1) where C is the combination function.
The polygon enclosed by either of the chain and the horizontal line attached to the chain is a convex polygon so it independently has Catalan(n-2) triangulations, therefore the total number of triangulations is Catalan(n-2)² C(2n-2,n-1). □