Exercise 3.19 For every n, construct a point set (not necessarily in general position) with n points whose flip graph is a single node, that is no flip is possible.
Solution. The boomerang(umbrella), or the crown(saw) for odd numbers. □
Exercise 3.20 For every n (greater than 3), construct a point set (not necessarily in general position) with n points whose flip graph is two nodes connected by an arc.
Solution. A properly organised boomerang shape with a spike sticking out from any of its shorter edges where the only flip can be made within the quadrilateral formed by it and the apex. □
Exercise 3.20 Figure 3.8 shows a triangulation for three different point sets. For each point set, find its flip graph.
Solution. (a) Only can flip in each of the three trapezoid; (b) quite a lot; (c) ... □
Exercise 3.23 Prove that if pn, a, and b are the only convex vertices in the star of pn, then the star of pn in T is exactly the star of pn in T*.
Proof. We prove it using Reductio ad absurdum. If they are different, there are two possible cases
- One is totally inside the other. It's easy to find that the bigger one must not be a valid star.
- The two reflex lines intersect somewhere. Then we can always pick points from the line between a and b other than the line passing through
pn , from the intersection of the two stars to form a star smaller than both of the two original so-called stars, and prove that they are actually not. □
Exercise 3.24 Prove or disprove: no point set can have a triangle as a subgraph of its flip graph, that is, three nodes connected in a cycle by three arcs.
Proof. Triangulation A flips and becomes B, if B flips on the same quadrilateral, it turns back to A and thus has no way to become a third triangulation C. Therefore B has to flip another quadrilateral, if it doesn't overlap the said one, then C cannot flip back to A since it's different than A in two quadrilaterals; if they overlap, C still cannot flip back to A since there are two different edges. □
Exercise 3.26 Find the diameters of the flip graphs of the point sets given in Figure 3.8.
Solution. (a) 3 (b) ... (c) ... □
Exercise 3.27 Find the diameter of the flip graph of the point set given in Figure 3.5.
Solution. (n-1)2 (where n is the number of vertices in each of the chains; proof and process omitted) □
Exercise 3.29 Figure 3.10 shows two triangulations from Figure 3.2 along with their overlapping diagram with 16 edge crossings. Verify Theorem 3.28 by finding a path in the flip graph between the two triangulations with no more than 16 flips.
Solution. Omitted. □
Exercise 3.30 Let S be a point set with h points on the hull and k points interior to the hull. Prove that the number of crossings of edges in T12 is at most (3k+h-3)2.
Proof. Actually this upper bound is too relaxed. Simply use the fact that the number of internal edges is 3k+h-3. □
Exercise 3.30 Show that this incremental algorithm indeed results in a partition of the convex hull into tetrahedral pieces.
Proof. May need first to clarify the difference between tetrahedralisation in this sense and that that is discussed in the previous chapter which is not feasible for some special point sets. The former is based on a set of points without any restriction on the 3D shape (polyhedron) they form, and the shape that the triangulation covers has to be the convex hull of the point set. Apart from this, the process of incremental algorithm generalised to 3D is simply collecting vertices in general position in the order determined by the lexicographical ordering to create a tetrahedralised set as it does with 2D. □
Exercise 3.33 If the point set S were not in general position, how would this affect the number of tetrahedra?
Solution. Vertices that happen to be on edges would split the tetrahedra that share the edge into two (if the edge is on the hull there would be two tetrahedra; if the edge is interior the number is indefinite (so the ultimate number may increase as opposed to the general position case); Vertices that happen to be on surfaces would split the one or two tetrahedra that contain the surface into three. □
Exercise 3.34 Based on the proof of the theorem, how can we find tetrahedralisations with fewer than 3k+2h-7 tetrahedra?
Solution. Start from a vertex with more than 3 incident hull triangles. (Since 3h < 2e, for all e > 6, can always find such a vertex according to pigeonhole principle) □
Exerciese 3.35 For arbitrary n > 4, construct an n-point set in R3 (not necessarily in general position) with a tetrahedralisation having at most n - 3 tetrahedra.
Solution. A n-point point set with all vertex other than one on the same plane.
Exercise 3.36 Let T be a point set consisting of the four vertices of a regular tetrahedron. Is it possible to add points P interior to T such taht the tetrahedralisation of the point set T U P results in only regular tetrahedra?
Answer. No. Even vertices are allowed to be added on the hull. As it were possible, the triangles on the hull would be triangulated into equilateral triangles which is possible and has to be done in such a way that all the triangles have their edges parallel to any of the three edges of the containing triangle. But based on this it would not build up a tetrahedralisation of regular triangles, since there is no way to tetrahedralise regular octahedra which remain after cutting into smaller regular tetrahedrons. □
Exercise 3.37 Constructs the flip graph of eight points in R3 whose convex hull forms a cube.
Solution. Should be interesting and not too difficult. Omitted. □
