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 9.7 (New edges are incident to \(p_r\))

  2. BCKO, Exercise 9.11 (Delaunay triangulations and Euclidean minimum spanning trees)

  3. BCKO, Exercise 10.7 (segment trees for vertical ray queries instead of window queries)

  4. BCKO, Exercise 11.8 (randomized incremental insertion for half-plane intersection)
    Note: this is not solving a linear program, as done in BCKO section 4.4, but rather computing the entire feasible region. Your algorithm should have expected running time similar to computing the convex hull in 2D.


537 Problem Set

  1. Consider the algorithm of Chapter 9 for computing Delaunay triangulations using randomized incremental insertion. As we know that Delaunay triangulations are dual to Voronoi diagrams, this suggests that there must be a randomized incremental insertion algorithm for Voronoi diagrams. Describe such an algorithm and prove it is correct. Specifically, you should focus on describing the algorithm to update \(\mathrm{Vor}(P_{r-1})\) by the insertion of the next point \(p_r\) to form \(\mathrm{Vor}(P_r)\). Prove this algorithm’s correctness and time complexity (you may, similar to in class, discuss the time complexity at a high level).

  2. BCKO, Exercise 9.13 (Delaunay triangulations and Gabriel graphs)
    Hint: Part b provides a connection between Gabriel graphs and acute triangulations from Homework 4.

  3. BCKO, Exercise 10.12 (deleting from segment trees and points in rectangles)

  4. BCKO, Exercise 11.9 (randomized incremental insertion for half-space intersection)
    Note: this is not solving a linear program, as done in BCKO section 4.4, but rather computing the entire feasible region. Your algorithm should have expected running time similar to computing the convex hull in 3D.


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 11.5 (3D Jarvis’s March)
    Note: to receive full credit for this exercise, a detailed description of the algorithm and its analysis is required.