COMP 258: Fall 1999



COMP258, Fall 1999: Homeworks

Problem Set #2, Due Weds, Sept 15.

Do two of the following three problems, and hand in your solutions either in class or anytime before midnight at my office sn333. Collaboration is permitted; good scholarship requires that collaborations be acknowledged.

  1. For the recursive selection procedure of Douglas and Peucker, analyze the expected running time under the assumption that whenever a fragment of a polygonal line is split, the splitting vertex is chosen with equal probability from the interior points of the fragment.
  2. Design an algorithm and data structure for line simplification that, given a tolerance, will produce a polygonal line that meets that tolerance. Ideally, the data structure should have linear size and the algorithm should produce a line with k segments in O(k) time.
  3. Consider the problem of simplifying either a river represented by two lines for its two banks, or a set of contour lines. Design an algorithm (at least at the pseudocode level, but if you want to implement it, then Ill provide data) that will simplify, but guarantee that the simplified curves do not intersect.