95.508 Computational Geometry. Due on April 14, 1997. For terminology and possible hints/solutions, refer to Mulmuley’s book (its on reserve in the library). Please do cite the sources which you are using to solve the final. Also if a group of students are trying to solve it together, please do identify the groups.

1. Consider a randomized incremental algorithm for computing the trapezoidal decomposition of n line segments. We insert segment by segment and maintain the trapezoidal decomposition H(N^{i}) and the conflict lists, at any stage i. In the class we defined the conflict list with respect to the end-points of the segments. But now we are going to change the definition of the conflict lists. For any trapezoid σ in H(N^{i}), the conflict list is the set of (non-inserted) segments, N − N^{i}, that intersects the trapezoid σ. Analyze the algorithm. For analysis you need to first assume that point location can be done, and then do the analysis and then analyze the expected cost of point location as well.

2. (Theorem 3.4.5, page 119) Recall the definition of configuration space π(N). For any j ≤ n, let e(j) denote the expected size of π(N^{j}), assuming that N^{j} is a random sample of N if size j. Let d, a constant, denote the maximum degree of a configuration in π(N). Show that the expected value of the total structural change in the randomized incremental construction is bounded by ∑_{j} de(j)/j. Also show that the expected value of total conflict change is bounded by ∑_{j} d^{2}[(n − j)/j](e(j)/j). Verify your answer to Question 1 using this result.

3. (Random Sampling theorem, Theorem 5.1.2, pp. 178) Prove the random sampling theorem. Let π(N) be any configuration space of bounded valence. Let d be the maximum degree, and n be the size of N. Let R be a random sample of size r. With probability greater than 1/2, for each active configuration in π(R), the conflict size of σ relative to N is at most c(n/r) log r, where c is a constant. More generally, fix any c > d. For any s ≥ r > d, with probablility 1 − O(1/s^{c−d}) the conflict size of each configuration in π(R) (relative to N) is less than c ln s/(r − d).

4. In the class we saw many examples of top-down sampling technique, e.g. the talk on polling technique. Show an example of bottom up sampling. A good candidate to try out will be skip lists. (Book has some other examples as well).

5. (furthests neighbor problem) Suppose we have a convex hull on nvertices in the plane. For each vertex, we want to know which is its furthest neighbor, i.e. the vertex in the convex polygon at the largest Euclidean distance. Give an algorithm (linear time ?) to solve this problem, i.e. for each vertex find its furthest neighbor.

6. (closest pair problem) Given a set of n points in the plane, find the closest pair. Give an algorithm that runs in O(n log n) time, what is the lower bound for this problem?