CIS 677: Homework 2, due about Oct. 13

1. Problem 2.14 of the text.
2. Problem 6.2 of the text.
3. Problem 6.3 of the text.
4. Problem 6.12 of the text.
5. Suppose a triangulation with n vertices is given; included in this input is the adjacency information of the triangulation. A point location data structure for the triangulation can be built by building the trapezoidal diagram of its edges using the randomized incremental algorithm. Show that this data structure can be built in O(n) expected time.
6. Let S be a set of line segments in the plane, with no three having a common crossing point, and no endpoints or crossing points with the same y coordinate. Let R be a random subset of S of size i. For trapezoid T of TD(R), let m_T be the number of segments of S that meet T. Let M be the sum of m_T over all trapezoids of TD(R). Show that the expected value of M is O(n+Ai/n), where A is the number of crossing segments of S. It will be helpful to know that the expected number of crossing points is exactly Ai(i-1)/n(n-1).