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.

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 7.12 (computing convex hulls from Voronoi diagrams)

  2. BCKO, Exercise 8.2 (more types of duals)
    Note: Be sure to clearly explain your answers.

  3. BCKO, Exercise 8.7 (finding separators)
    Hint: While there is a “direct” solution to this problem that can be formulated in the primal plane, it may be easier to think of this question in terms of the dual.
    Hint #2: Both solutions will appeal to another problem we found could be solved in \(\mathcal{O}(n)\) expected time.

  4. BCKO, Exercise 9.4 (smallest angles in completions)
    Hint: Consider the case for four cocircular points first, and then argue that this generalizes to any number of points.


537 Problem Set

  1. BCKO, Exercise 8.9 (convex hulls from arrangements)
    Hint: see Exercise 8.7.

  2. BCKO, Exercise 8.16 (stabbing segments)

  3. A triangulation of a set of points \(P\) in the plane is acute if the angles of all of its triangles are strictly acute, that is less than \(\pi/2\). Prove that:

    • Any acute triangulation of \(P\) is a Delaunay triangulation of \(P\)

    • If \(P\) has an acute triangulation, than \(\mathrm{Vor}(P)\) has the following property: the interior of each Voronoi edge intersects its dual Delaunay edge.

  4. BCKO, Exercise 9.3 (transforming triangulations via edge flips)
    Instructor’s Note: while the book’s “hint” is one way to approach this problem, one could also instead rely on the algorithm LegalTriangulation().