## 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)