Homework 2
Chs. 35
Due: Feb. 20, 2019 01:59:59 PM
Graded: Feb. 27, 2019
Percentage of Grade: 10%
Assignment Description: Finalized
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

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

BCKO, Exercise 3.6 (splitting polygons with triangulations)

BCKO, Exercise 4.10 (redundant halfplanes)

BCKO, Exercise 4.15 (starshaped polygons)

BCKO, Exercise 5.4a,b,c (partial match queries: only complete parts a,b,c)
537 Problem Set

BCKO, Exercise 3.10 (triangulating a set of n points)
Hint: Start by computing the convex hull, and considering splitting the resulting polygon into subpolygons. 
BCKO, Exercise 3.11 (determining if a polygon is monotone in any direction)

BCKO, Exercise 4.10 (redundant halfplanes)

BCKO, Exercise 4.16 (leading trains)

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