## 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.