ICS 266, Spring 1996, Homework Set 4

Due Thursday, May 30, in class

1. Incremental and randomized incremental algorithms. A trapezoidal decomposition of a polygon is formed by drawing a vertical line segment up and down through each vertex of the polygon, extending until it reaches the polygon boundary. The trapezoidal decomposition of a line arrangement is formed by performing this process in each cell of the arrangement.
   • Show how to modify the incremental line arrangement algorithm we discussed in class to compute trapezoidal decompositions, in the same overall O(n^2) time bound.

   • Show how to use a history graph of these trapezoids, in which we store (for each trapezoid formed at any stage of the algorithm) a description of the event causing the trapezoid to stop being part of the decomposition, to perform point location queries in this decomposition. What types of events can occur? How much space does the data structure use? What is the worst case query time of your data structure?

   • Show that if the lines are added in random order, the history graph can be used to perform point location queries in O(log n) expected time.

   • What goes wrong if we try to simplify this point location data structure, by using cells in the arrangement rather than trapezoids of the decomposition, and storing (for each cell formed at any stage of the algorithm) a pointer to the first line cutting it and the two cells it is cut into?

2. Linear programming and LP-type problems.

   Recall that an LP-type problem is defined by a set S and a function f mapping subsets of S to some totally ordered space, satisfying the following two properties:

   • If A is a subset of B, then f(A) <= f(B).
   • If f(A)=f(A u {x})=f(A u {y}), then f(A)=f(A u {x,y}).

   A basis of the problem is a set B such that for any proper subset A, f(A) < f(B). The dimension of the problem is the size of the largest basis. The answer to a problem consists of the value of f(S), or equivalently max_B f(B) where the maximization occurs over all bases. In class we saw randomized algorithms for solving such problems using a number of basis evaluations linear in |S| and exponential in the dimension.

   • Suppose we have two sets of points S and T in three-dimensional space, and we wish to determine whether some plane separates S from T. Can you express this as an LP-type problem? As a low dimensional linear program? (Hint: use projective duality.)

   • Suppose we have solved the first part, and know that a plane separates S from T; then their convex hulls must be disjoint. Show how to express the problem of finding the closest pair of points x and y, with x in the convex hull of S and y in the convex hull of T, as an LP-type problem. What is its dimension? (Note: x and y might not be part of the input sets S and T, they can be any points contained in the respective convex hulls. You can assume that the points are in general position e.g. no two faces of the convex hulls are parallel.)

   • The problem of finding the closest pair s in S and t in T is not LP-type, even if you know that the convex hulls of S and T are disjoint. Which property defining LP-type problems is violated?

3. Dynamic programming.
   [Corman, Leiserson, and Rivest, "Introduction to Algorithms", problem 16-1, p. 324.]

   The Euclidean traveling-salesman problem is the problem of determining the shortest closed tour that connects a given set of n points in the plane. The general problem is NP-complete. J. L. Bentley has suggested the problem by restricting our attention to bitonic tours, that is, tours that start at the leftmost point, go strictly left to right to the rightmost point, and then go strictly right to left back to the starting point. (Equivalently, any vertical line should cross the tour at most twice.)

   Describe an O(n^2)-time algorithm for determining an optimal bitonic tour. You may assume that no two points have the same x-coordinate. (Hint: Scan left to right, maintaining optimal possibilities for the two parts of the tour.)

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