In computer graphics, triangulations are used to represent surfaces. Graphics libraries like OpenGL support a special type of triangulation called a strip, which is defined as follows. For n 3, given a sequence of vertices V = (v, 2,..., Un), the strip of V consists of the n-2 triangles (vi, Vi+1, Vi+2), for 1 in-2. See Figure 1. VIO 12 13 15 Figure 1: An x-monotone strip polygon. Assume that you are given an n-sided, z-monotone simple polygon P as a sequence of vertices in counterclockwise order. 1. Give an algorithm to decide if P can be triangulated as a strip of the form given above. 2. Give a rigorous proof of correctness and derive the running time of your algorithm. Note: The r-monotonicity will play a significant role in your algorithm and its proof of cor- rectness. There is a simple linear time algorithm for this problem, but the proof of correctness is not completely straightforward. Your algorithm need not run in linear time. However, a more efficient algorithm will receive more credit.