Instructions

Please assume all instructions, rules, and regulations from Homework 1 to still apply for this problem set, with the following exception. Each problem set will now only contain 4 questions, each weighted at 25% of the point value for the assignment. Extra credit questions are still weighted at 5% of the point value for the assignment. Students in 437 may still attempt any of the 537 questions for extra credit, and students in 537 may still attempt any of the 437 questions for extra credit.

As an added bonus, students from either section may attempt the additional extra credit question listed at the end of the assignment for 10% of the point value of the assignment.

Please otherwise review these instructions before your start, including details on our expectations for proofs and all rules and regulations.


437 Problem Set

  1. BCKO, Exercise 12.12a (BSP trees compared to kd-trees: only complete part a)

  2. BCKO, Exercise 13.2 (road maps with no center nodes)

  3. BCKO, Exercise 14.3 (non-obtuse triangulations from quadtrees are Delaunay triangulations)

  4. BCKO, Exercise 15.6 (shortest paths for two points inside of a simple polygon)


537 Problem Set

  1. BCKO, Exercise 12.11a,b (using BSP trees for other tasks: only complete parts a,b)

  2. BCKO, Exercise 13.5 (Minkowski sums of convex polygons are equivalent to the convex hulls of Minkowski sums of vertices).

  3. BCKO, Exercise 14.8 (balanced quadtrees while constructing)

  4. BCKO, Exercise 15.7 (shortest paths for convex polygons)


Extra Credit Problem

In addition to completing the exercises from the other section of the class at 5% extra credit per question, every student is eligible to complete the following question worth 10% extra credit.

  1. BCKO, Exercise 14.14 (quadtrees vs. kd-trees vs. range trees)