Instructions

Please assume all instructions, rules, and regulations from Homework 1 to still apply for this problem set, unless otherwise stated. You may want to review them before you start.

Note that question 3 (BCKO 4.10) is repeated in both problem sets.


437 Problem Set

  1. BCKO, Exercise 3.3 (dual graphs of triangulations of monotone polygons)

  2. BCKO, Exercise 3.6 (splitting polygons with triangulations)

  3. BCKO, Exercise 4.10 (redundant half-planes)

  4. BCKO, Exercise 4.15 (star-shaped polygons)

  5. BCKO, Exercise 5.4a,b,c (partial match queries: only complete parts a,b,c)


537 Problem Set

  1. BCKO, Exercise 3.10 (triangulating a set of n points)
    Hint: Start by computing the convex hull, and considering splitting the resulting polygon into sub-polygons.

  2. BCKO, Exercise 3.11 (determining if a polygon is monotone in any direction)

  3. BCKO, Exercise 4.10 (redundant half-planes)

  4. BCKO, Exercise 4.16 (leading trains)

  5. BCKO, Exercise 5.10a,b (range counting queries: only complete parts a,b)