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?)
How long does your algorithm take?
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?)
(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.)
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.
(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.
