# HW1
## Problem 1
 - 1. In this graph, there are 3 forced diagonals (7-12, 6-14 and 5-17) which divide this graph in to 4 parts. For the right most part it is a blunt nose fox so it has 4 ways of triangulations; for the second one there is only one way because it is a fox; the third one is again, a blunt nose fox with 4 ways; as for the last part we have to do case analysis:
       - 1. use 4-17 but not 2-5: there are two convex polygon with 3 and 6 vertices, so there are 14*1=14 ways to triangulation
       - 2. use 2-5 but not 4-17: for the graph under 2-5, it is a convex polygon with 4 vertices so there are 2 ways; for the upper part, 2-17 is a forced diagonal so it can be treated as a 4 vertices polygon so overall it has 2*2=4 ways
       - 3. not use both 4-17 and 2-5: for the last situation, 3-17 is a forced diagonal so it has 5\*1\*1=5 ways

      Overall, there are 4\*1\*4\*(14+4+5)=368 distinct ways to triangulation this graph

 - 2. In this graph, there are a pair of diagonals that are mutual exclusive: 1-6 and 0-2, if we do case analysis based on that:
      - 1. use 1-6: the left side is a convex polygon with 8 vertices so it has 6 ways; the right side is a blunt nose fox so it has 4 ways
      - 2. use 0-2: then there are two forced diagonals (0-6 and 2-6). If we connect them, then there is a convex polygon with 7 vertices on the left and a fox on the right. In total, there should be 1\*1\*1\*42 ways

      Over all, there are 132*4+42=570 distinct ways of triangulations.

## Problem 2
 - 1. 
      - 1. ![2_1_1](2_1_1.png)
      - 2. As the graph above, there are 6 reds, 6 blues and 7 yellows, then we put guards on either reds or blues and we can get 6 guards.
      - 3. ![2_1_2](2_1_2.png)
          If we put witness points near 18, 2, 7 and 10, and in between 4 and 5, we got 5 areas that does not overlap on any vertex, $w(P) \geq 5$. Also, we can find 5 guards A, B, C, D and E that cover P, thus $g(P) \leq 5$

            $5 \leq w(p) \leq g(p) \leq 5$, and we can get $g(p) = 5$
      - 4. ![2_1_3](2_1_3.png)
          If we put witness points near 18, 2 and 7, and in between 4 and 5, we got 4 areas that does not overlap, so $w(P) \geq 4$. Also, we can find 4 guards A, B, C and D that cover P, thus $g(P) \leq 4$

            $4 \leq w(p) \leq g(p) \leq 4$, and we can get $g(p) = 4$
 - 2. 
      - 1. ![2_2_1](2_2_1.png)
      - 2. As the graph above, there are 8 reds, 8 blues and 8 yellows, then we put guards on any of reds, yellows or blues and we can get 8 guards.
      - 3. ![2_2_2](2_2_2.png)
          If we put witness points near 3, 10, 17 and 23, and in between 13 and 14, we got 5 areas that does not overlap on any vertex, $w(P) \geq 5$. Also, we can find 5 guards A, B, C, D and E that cover P, thus $g(P) \leq 5$

            $5 \leq w(p) \leq g(p) \leq 5$, and we can get $g(p) = 5$
      - 4. ![2_2_2](2_2_2.png)
          If we put witness points near 3, 10, 17 and 23, and in between 13 and 14, we got 5 areas that does not overlap, $w(P) \geq 5$. Also, we can find 5 guards A, B, C, D and E that cover P, thus $g(P) \leq 5$

            $5 \leq w(p) \leq g(p) \leq 5$, and we can get $g(p) = 5$