Problem 1. Given two point sets (A,B) each with N points. Define an efficient algorithm (better than O(n2) which finds the closest pair of points with one from A and one from B.
(Hint: if b is the closest point in B to point a, what do you know abou the locations of other points in B?... if a is the closest point in A to b, what do you know about the location of other points in A?)
Potential algorithm: (there are several).
1. Compute the voronoi diagram of the point set B.
2. minDist = Infinity, bestPair = {}.
3. For each point a in set A
Use the voronoi diagram to find the point b in set B which is
closest to a.
If dist(a,b) < minDist, then
minDist = dist(a,b), and bestPair = (a,b).
endIf
end loop.
return bestPair.
How long does your algorithm take?
Step One: Voronoi diagram is O(n log n). Step three: n times through a loop. each iteration taked O(log n) for total time of O( n log n). Problem 2. Given a set P of n points in the plane, and given any slope theta, project the points orthogonally onto a line whose slope is theta. The order (say from top to bottom) of the projections is called an allowable permutation. (If two points project to the same location, then order them arbitrarily.) For example, in the figure below, for the slope theta the permutation would be (p1, p3, p2, p5, p4, p6).
(a) Prove that there are O(n2) distinct allowable permutations. (You can solve this either in the primal plane, or by using a dual transformation. What does an allowable permutation correspond to in the dual plane?)
In the dual plane, a vertical line corresponds to a set of parallel lines in the original plane. An allowable permutation corresponds to the ORDER in which a vertical line intersects the dual lines (the representations of the points). This order changes only when two lines intersect each other, this happens O(n2) times.
(b) Give an O(n3) algorithm which lists all the allowable permutations for a given n-point set. (O(n2) time to find the permutations and O(n) time to list each one.)
Done in class today ;).
Problem 3: We say that a line l bisects an n-element planar point set A, if each of the two closed halfspaces defined by l contains at least floor(n/2) points of A. (If n is odd, we may assume that one point of A lies on l and the other points are equally partitioned by l.) Given two points sets A and B, a ham sandwich cut is a line that simultaneously bisects both point sets.
(a) Give an algorithm, which given two planar point sets A and B, of
total size n, computes a ham-sandwich cut in O(n2) time.
Done in class today ;).
Consider one of the sets, say A. Observe that for each slope there
exists one way to bisect the points. In particular, if we start a line
with this slope at positive infinity, so that all the points lie
beneath it, and drop in downwards, eventually we will arrive at a
unique placement where there are exactly (n - 1)/2 points above the
line, one point lying on the line, and (n - 1)/2 points below the line
(assuming no two points share this slope). This line is called the
median line for this slope.
What is the dual of this median line? If we dualize the points using
the standard dual transformation: then we get n lines in the plane. By
starting a line with a given slope above the points and translating it
downwards, in the dual plane we moving a point from -infinity upwards
in a vertical line. Each time the line passes a point in the primal
plane, the vertically moving point crosses a line in the dual
plane. When the translating line hits the median point, in the dual
plane the moving point will hit a dual line such that there are
exactly (n-1)/2 dual lines above this point and (n - 1)/2 dual lines
below this point. We define a point to be at level k in an
arrangement if there are at most k - 1 lines above this point and at
most n - k lines below this point. The median level in an arrangement
of n lines is defined to be the ceiling((n - 1)/2)-th level in the
arrangement. Lets call this M(A).
Thus, the set of bisecting lines for set A in dual form consists of a
polygonal curve in the dual plane. Similarly, the set of bisecting
lines for set B (M(B)) create a polygonal curve in the dual plane. Both
of these curves are x-monotone (any vertical line only intersects this
line once). Finding the intersection of 2 x-monotone polygonal curves
can be done as follows:
1) find the (infinite) segments at the left edge of M(A) and M(B).
define the "current segments for a and b" C(a) and C(b) to be these
infinite segments.
2) Do C(a) and C(b) intersect?
If so report that intersection as the ham-sandwich cut and halt.
If not, then
if segment C(a) has a smaller x-coordinate for its right endpoint,
update C(a) to the next segment in the M(A) polygonal chain.
else
update C(b) to the next segment in the M(b) polygonal chain.
end
endif
goto step 2
(b) You are given two sets A and B of points in the plane, both of size n. Assuming that a ham-sandwich cut can be computed in O(n log n) time, give an O(n log2n) algorithm that outputs a set of pairwise disjoint line segments, each connecting a point of A to some point of B.
Done in class today ;).
