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 437 question 1 (BCKO 6.8) is repeated as 537 question 2.


437 Problem Set

  1. BCKO, Exercise 6.8 (deterministic trapezoidal maps with plane sweep)

  2. BCKO, Exercise 6.10 (finding shear transformations)

  3. In Lecture 11, we showed in class that if a point \(p \in P\) is a vertex of \(\mathrm{CH}(P)\) then the Voronoi cell of \(p\) in \(\mathrm{Vor}(P)\), \(V(p)\), is unbounded. Prove the converse: if \(V(p)\) is unbounded in \(\mathrm{Vor}(P)\), then \(p\) must be a vertex of \(\mathrm{CH}(P)\).

  4. BCKO, Exercise 7.2 (number of vertices of a Voronoi cell)

  5. BCKO, Exercise 7.10 (closest pair of point, revisited)
    Hint: this is now easier than it was when we considered this problem in Lecture 01.


537 Problem Set

  1. BCKO, Exercise 6.5 (fast testing of inside-outside for convex polygons)

  2. BCKO, Exercise 6.8 (deterministic trapezoidal maps with plane sweep)

  3. BCKO, Exercise 7.3 (sorting reduced to Voronoi)
    Hint: for those of you not used to reductions, the idea is that given a set of numbers, \(S\), construct a set of points \(P_S\) (in time \(\Omega(n\log n)\)) whose Voronoi diagram can be used to determine the sorted order of \(S\).

  4. BCKO, Exercise 7.7 (breakpoint movement)

  5. BCKO, Exercise 7.11 (all closest pairs)
    Hint: see Exercise 7.10.