CS507: Computational Geometry
Instructor: Godfried Toussaint
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.
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 2n.
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.
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
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.