Solution: See attached graph paper sheet.

Draw the Voronoi diagram of 10 random points in the plane using the L-1 metric instead of the L-2 metric for defining inter-point distances. Show an example of a Voronoi cell that is not convex.

Solution: See attached graph paper sheet.

Show that the closest pair of points

Solution: See attached graph paper sheet.

The

whered(p,S) = min {d(p,q):qis inS},

and theH(A,B) =max{d(a,B):ais inA},

This metric is used to measure similarity between two sets of points. Outline an efficient algorithm for computing the Hausdorf distance between two sets,D(A,B) =max{H(A,B),H(B,A)}.

Solution: By symmetry it is clearly sufficient to devise an algorithm
that computes the

directed Hausdorff distance *H(A, B)*.

We start by computing the decomposition of the Euclidean plane in Voronai
cells defined by the set *B*. We know that can be achieved
in *O(n log(n))* in a variety of ways. This decomposition
of the plane has *O(n) *edges and vertices. For each point
in *A * we wish to determine in which cell of the Voronai
decomposition it lies. Thus we need to process further the Voronay
decomposition to implement an efficient solution to the *point
location problem. *We know the existence of solutions which require
an extra preprocessing time of order *O(n) *or at worst, *O(nlog(n)).*

After the preprocessing step, we examine *A. *For each
*a * in *A * we can perform the query: "In which
Voronay cell *a *lies?" in *O(log(n))*
time. This query is equivalent to: "What is the point in *B*
closest to *a *?". We apply this procedure to every point
in *A, *thus computing *distance(a, B)* for each
*a*. This whole computation runs in *O(nlog(n)) *
time.

Finally, *H(A, B) *is the maximum of the values *distance(a,
B)*, by definition.

Since each of the above (preprocessing, querying, minimum) stages in
our computation took

total running time *O(nlog(n))*, this is the running
time of the whole algorithm.

Suppose you are given a set

Solution: Before we go into the algorithm itself, let's analyze
the possibilities for the location

of the center of the largest circle with center in *R*.
We break into cases according to how many

points of *S *are located at the boundary of this
circle *C*. At points in our argument we will make use
of the Voronai decomposition of the plane generated by the point sites
in * S. *If *P *denotes a site in
*S* the Voronai cell containing * P *will be
denoted by *B _{P} .*

Case 1: There are 0 or 1 points of * S * in the
boundary of * C.* This case may happen only if the center
of *C * is one of the corners of the rectangle; if,
for instance there is 1 point *P * in the boundary of *
C, * and *C's * center lies inside an edge of the
rectangle, moving the center of *C* along that edge in
the direction away from *P * creates a circle with larger
radius than *C, * a contradiction. The other cases
(0 points in the boundary or center within *R *) are easier
applications of the same reasoning. By finding the point in *
S *closest to each corner we thus determine the largest circle *
C * centered on a corner in time of order *O(n).*

Case 2: The circle might contain 2 points in its boundary, call
them * P * and * Q*. It is easy to show
then that if the center of * C * did not lie in the boundary
of *R, * a small enough displacement of *C's*
center along the radial direction orthogonal to the chord *PQ*
would give rise to a larger circle, which contradicts the maximality of
*C*. So the center of *C *lies in the boundary
of *R, *and in fact by a property of circles we just invoked,
it lies also in the radial line bissecting the chord *PQ.
*Now, the midpoint of this chord *PQ * is a point in
the edge shared by neighbor Voronai cells *B _{P}
*and

The hard case thus is when the circle has center in the
interior of *R*, which implies it contains at least three
points of * S *in its boundary. We make the simplifying
assumption that * C * contains exactly 3 points in its boundary,
though the general case is not different in essence. The triangle
formed by these points is thus a face of the Delaunay triangulation, by
the empty circle property.

We thus perform an exhaustive search in all bounded faces
in the D.T., computing the circumscribing circle of each face.
So even this case runs in linear time, because there are *O(n)*
faces.

Conclusion: The algorithm finds the largest circle
in each corner, the largest circle with center in intersections of
Voronai edges and the boundary of rectangle * R, * and the
largest circumscribing circle of each face in the Delaunay triangulation
and compares all these circles to find the maximum. This whole computation
takes time of order *O(n). * Constructing the Delaunay triangulation
and Voronai decomposition as a preprocessing step takes order *O(n
log(n))*. Thus

the running time of the whole algorithm is bounded by *
O(n log(n))*.