Due 4pm Wds Oct 12 in the Homework Box in 2131 Kemper Hall.

1. Here is a problem:

Input: A set P of points in the plane.
Output: The smallest ball containing three or more points of P.

Describe how the algorithm for closest pair in Section 33.4 can be modified to solve this problem in O(n lg n) time. You do not need to describe steps which are not changed in detail. Give the best upper bound you can (give a formal proof!) on the number of points which must be compared with each point in the strip (7 for the algorithm in the book). Notice that the minimum enclosing ball for a set of three points in the plane might touch two of the points, or three, as in the picture above (the fact that the balls are the same size in this picture is irrelevant). The notes on the arguement we used for the closest pair algorithm might be helpful.

2. In Section 33.4, there is a comment that the recurrence relation

T(n) = 2 T(n/2) + a (n lg n)
T(1) = O(1)

solves to O(n lg² n). Prove this by substiution (Section 4.1). Do not use the Master Method (Section 4.3).

3. Prove that the function log_kn is O( log₂ n), for any k>1. Use the definition of Big-O and give the constant c explicitly. You might want to check out the material on logarithms in Section 3.2.

4. Do problem 4-7 at the end of Chapter 4. Juan will do part a in Section; you take it from there. Notice that the rows are numbered 1...m from top to bottom. You may assume that m is a power of two (it makes the math easier).