600.488 Homework Assignment 6
Due: Wednesday, April 7, 1999
All the problems of this homework assignment
have to do with the farthest-point Voronoi diagram.
Define the farthest-point Voronoi diagram as the union of
farthest-point 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
Give an example of a set S and a point p in S
Show that each non-empty region in a farthest-point Voronoi diagram is
unbounded and associated with a point on the convex hull of S.
Define the farthest-point Delaunay Triangulation as the
graph-theoretic planar dual of the farthest-point Voronoi diagram.
Derive a relationship between the
farthest-point Delaunay Triangulation and the convex hull of the
3-dimensional set of points defined by mapping each point
(x,y) in S to the point
Use this fact to design a simple O(n log n) time
algorithm for constructing a fathest-point Voronoi diagram.
Prove that each vertex v of the farthest-point 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 farthest-point Voronoi diagram to compute the
smallest-radius 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?