600.488 Homework Assignment 5

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?

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 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.

Solution: See attached graph paper sheet.

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?

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 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?

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 B_Q. These cells are indeed adjacent because the existence of the empty circle C implies that the chord PQ is an edge in the Delaunay triangulation. The center of C is another point in the edge between B_P and B_Q , since by construction P and Q are equidistant from C's center and no other site in S is closer to this center. So the whole segment connecting C's center to the midpoint of PQ is part of an edge in the Voronai decomposition. This implies we can search for such circles C by considering the intersections of edges in the Voronai decomposition with the boundary of the rectangle. Since there are O(n) edges to examine, checking this case also runs in linear time.

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)).