600.488 Homework Assignment 6
Due: Wednesday, April 7, 1999
All the problems of this homework assignment
have to do with the farthestpoint Voronoi diagram.
Define the farthestpoint Voronoi diagram as the union of
farthestpoint cells, where we define for each point p in a
set S of n points the cell F(p) to be the
set of all points that have p as their farthest neighbor in
S.

Give an example of a set S and a point p in S
such that
F(p)
is empty.

Show that each nonempty region in a farthestpoint Voronoi diagram is
unbounded and associated with a point on the convex hull of S.

Define the farthestpoint Delaunay Triangulation as the
graphtheoretic planar dual of the farthestpoint Voronoi diagram.
Derive a relationship between the
farthestpoint Delaunay Triangulation and the convex hull of the
3dimensional set of points defined by mapping each point
(x,y) in S to the point
(x,y, x^{2}+y^{2}).
Use this fact to design a simple O(n log n) time
algorithm for constructing a fathestpoint Voronoi diagram.

Prove that each vertex v of the farthestpoint Voronoi diagram
corresponds to a circle C determined uniquely
by the sites defining v
such that C contains all the points of S.

Show how to use the farthestpoint Voronoi diagram to compute the
smallestradius circle that contains all the points of S.
(Hint: the smallest one might be determined by only two points in S.)
What is the running time of your method?