600.488 Homework Assignment 5
Due: Wednesday, March 31, 1999

Draw the Voronoi diagram of 10 points all on a line.
Draw separately the Voronoi diagram of 10 points all
on a circle.
What do these two diagrams have in common?

Draw the Voronoi diagram of 10 random points in the plane using the
L1 metric instead of the L2 metric for defining interpoint
distances.
Show an example of a Voronoi cell that is not convex.

Show that the closest
pair of points p and q in a set of points
in the plane have neighboring cells in this set's Voronoi diagram.
That is, the Voronoi cell for p must share an edge with the
Voronoi cell for q if they are the closest pair in the set.

The set distance from a point p to a set of points S
is defined as
d(p,S) =
min {d(p,q):
q is in S},
where d(a,b) is the
normal Euclidean distance from a to b.
The directed Hausdorf distance from a set of points A to
a set of points B is
H(A,B) =
max {d(a,B):
a is in A},
and the Hausdorf distance between a set of points A and
a set of points B is
D(A,B) =
max {
H(A,B),
H(B,A)}.
This metric is used to measure
similarity between two sets of points.
Outline an efficient algorithm
for computing the Hausdorf distance between two sets, A and B,
each containing n points in the plane.
What is the running time of your method?

Suppose you are given a set S of n points in the plane
and a rectangle R containing all these points in its interior.
Describe an efficient algorithm for finding the largest circle
that has its center inside R but contains none of the
points of S in its interior (i.e., it is an empty circle).
What is the running time of your method?