Exam 2 - Solutions - 2001

(Solutions by Greg Aloupis)
NOTE: These are only sketches of solutions. I expect to see more details during exams.

Question 1:

See class notes.

Question 2:

a) Consider the figure below. Place four points (a,b,c,d) on a circle as shown on the left. Their furthest-point Voronoi regions (A,B,C,D) are separated by the dashed lines. Now move c along the line from b to c by some small amount, and move a symmetrically, so that we obtain the configuration shown in the middle. The light blue region is the Voronoi site of c. I'm sure it is clear to everyone that the bisection of b and c has shifted to the left, and the bisection of c and d has rotated counterclockwise and shifted to the right. The site belonging to a will be symmetric, so the sites of b and d will not be adjacent. However, b and d form the diameter of these points.
 

b) Consider the figure below, where we have two blue points which determine the diameter of a circle. There can be at most one more point on the circle, and we color it red. I claim that the center of the circle belongs to the furthest-Voronoi sites of both blue points: if we take any other point (shown black) that is strictly inside the circle, we can take the segment from the left blue point to the black point and extend it until it intersects the circle. The bisection of this intersection and the left blue point passes through the center. Thus the bisection of the left blue point with a black point must pass strictly to the left of the center. Therefore no black point can "claim" the center. The same applies symmetrically for the other blue point. Thus the center belongs to the Voronoi sites of the blue points, and possibly one red point if it exists. Note that since only three regions can meet at one point, the Voronoi-sites of the blue points share a common edge.
 

Question 3:

Base case: without loss of generality, suppose that the empty cell is in the top-right quadrant of the square. Then fill in one L-shape as shown below, and the remaining four L-shape positions are uniquely determined.

General case: suppose we are given a square of width 2ⁿ. Again, suppose that the empty cell is in the top-right quadrant. Then split the square into its quadrants, place one L-shape in the middle as shown, and solve four problems of size n-1.
 

Question 4:

a) It is easy to perform a binary search on the vertices of a convex polygon, to determine which point (or edge) of the polygon is closest to an exterior point p. See the figure below: if we take the two tangent lines to the polygon, we form two chains, red and blue. Any time we look at a vertex, we can tell if it is red or blue by the angles of its neighboring edges. Thus we can perform a binary search to find the top or bottom tangent point. The distance from p to the blue chain is unimodal, so again a binary search will suffice. Since we can find the minimum distance in O(logn) time, the lower bound given is incorrect.

b) The distance from a point q to the boundary of a polygon that encloses q is multimodal. For example, in the figure below, there are n points on the polygon's boundary at unit distance from q. However, if we perturb one of the polygon's vertices, there will be only one point with minimum distance to q. Determining which point is perturbed requires Omega(n) time.