Problem Set 7 flaming g flaming 8 Chasm of Chasm of Hideous Hideous Death Death A Safe Path An unsafe path Show that there are exactly Cn safe paths by describing a bijection with balanced parentheses strings (c) Many computational geometry algorithms begin by partitioning polygons into triangles with the same vertices. For example, here are all the possible triangulations of a pentagon Show that there are Cn different ways to triangulate a convex (n+2) -gon by describ ing a bijection from triangulations to balanced parentheses strings. (This problem is challenging, ask your TA for help if you're stuck Solution. Note that every nonempty balanced parentheses string has the form(a)B since the first symbol must be( and there must be a matching ). Thus, every bal- anced parentheses string can be decomposed into two smaller strings a and B. We'll exploit this fact to recursively map a balanced parentheses string to a triangulation Suppose we have a not-yet-triangulated(n+ 2)-gon and a balanced parentheses string(a)B. We must map the parentheses string to a triangulation. Select two consecutive vertices a and y and denote the remaining vertices vor Un-1. It must be that a contains j pairs of parentheses and B contains the remaining (n-1)-j pairs for some j between 0 and n-1. Draw a triangle with the vertices ,y, and vProblem Set 7 7 � � � �� �� � � � � � � Flami Chasm of ng � � Hideous �� Death �� � �� �� � � � � �� � � Fl C ami has ng m of � � Hideous �� Death �� A Safe Path An Unsafe Path Show that there are exactly Cn safe paths by describing a bijection with balanced parentheses strings. (c) Many computational geometry algorithms begin by partitioning polygons into triangles with the same vertices. For example, here are all the possible triangulations of a pentagon: B B Q     QQQ  QQQQ  B B QQQQ  QQQQ  QQ  B   B   QQ c B C Cc C B C # C # C c B C c C B C # C # C cc B C c C B C ## C ## C c B C cc C B C # C # C cB C c C B C# C# Show that there are Cn different ways to triangulate a convex (n+2)­gon by describ￾ing a bijection from triangulations to balanced parentheses strings. (This problem is challenging; ask your TA for help if you’re stuck!) Solution. Note that every nonempty balanced parentheses string has the form (α)β since the first symbol must be ( and there must be a matching ). Thus, every bal￾anced parentheses string can be decomposed into two smaller strings α and β. We’ll exploit this fact to recursively map a balanced parentheses string to a triangulation. Suppose we have a not­yet­triangulated (n + 2)­gon and a balanced parentheses string (α)β. We must map the parentheses string to a triangulation. Select two consecutive vertices x and y and denote the remaining vertices v0, . . . , vn−1. It must be that α contains j pairs of parentheses and β contains the remaining (n − 1) − j pairs for some j between 0 and n − 1. Draw a triangle with the vertices x, y, and vj .