ICS 266, Spring 1996, Homework Set 3

Due Tuesday, May 14, in class

1. Plane sweep. Suppose you are given a collection of circles in the plane, none of which cross each other. Describe an algorithm for testing whether there is any pair of circles, one of which contains the other. What is the running time of your algorithm?

2. Davenport-Schinzel Sequences. Any two ellipses can have at most four crossing points. What does this imply about the complexity of a lower envelope of n ellipses? How quickly can one compute such a lower envelope?

3. Ham-Sandwich Trees. A Ham-Sandwich tree in the plane works by cutting the point sets corresponding to the two children of any node by a common line; the result is that any halfplane boundary can only cross three out of the four grandchildren, so this data structure gives fast halfspace range queries. More explicitly, if we let T(n) denote the query time on this data structure, and S(n) denote time to query a node for which one of its two children is missed by the query boundary, we have a recurrence

   T(n) = T(n/2) + S(n/2) + O(1)
   S(n) = T(n/2) + O(1)

   which has a solution involving the Fibonacci numbers.

   In three dimensions, we would like to perform an analogous construction, in which we cut the point sets corresponding to the four grandchildren of any node by a common plane.

   (a) If this were possible, what would this imply about halfspace range queries? Write out a recurrence for the query time and solve it.

   (b) Show that it is not possible i.e. find four point sets that can not be evenly cut by a single plane.

ICS 266, David Eppstein, Dept. Information & Computer Science, UC Irvine
Last update: 07 May 1996, 10:10:38 PDT