CS 497: Computational Geometry

Homework Problems

  1. [January 18] Describe an algorithm to construct the convex hull of two convex polygons in O(n) time, where n is the total number of vertices in the input.

  2. [January 20] A simple polygon is a circular sequence of line segments joined end-to-end with no other intersections.
    1. The "three-penny algorithm" from Graham's scan computes the convex hull of some simple polygons, but not all. Describe a simple polygon P for which the three-penny algorithm fails to produce the convex hull.
    2. Describe an algorithm to construct the convex hull of any simple n-vertex polygon in O(n) time. This is harder than it looks!

    A simple polygon (green) and two nonsimple polygons (red)

  3. [January 25] Describe an O(log n)-time algorithm to find the two tangent lines of a convex n-gon that pass through a point outside the polygon. Assume the polygon vertices are stored in an array in counterclockwise order.

  4. [January 27] Describe an algorithm that determines in linear time, given a Voronoi diagram with n regions, the set of n points that define it. [Hint: Try n = 4.] You should be able to describe your algorithm purely purely geometrically, without using any of the ugly algebra that would show up in an actual implementation. What does your algorithm do if we give it a planar map that is not a Voronoi diagram?

  5. [February 1] Describe an infinite sequence S of planar sites p1, p2, p3, ..., such that for all n, the Voronoi region Vor(pn, Sn) has n-1 edges. This is a worst-case input for any incremental Voronoi diagram algorithm. Here, Sn denotes the first n sites in the sequence S, and Vor(p,A) is the Voronoi region of a site p with respect to a set of sites A.

  6. [February 1] Show that in Fortune's sweep-line algorithm for constructing planar Voronoi diagrams, the "beach line" consists of at most 2n-1 parabolic segments. [Hint: Two horizontal parabolas intersect in at most two points.]

Open Problems

  1. [January 20] Describe an algorithm that finds, given a set of n points in the plane, the median vertex of its upper convex hull, in O(n) time. A randomized algorithm that usually finds an approximate median is fine. Such an algorithm would lead to a variant of quickhull that runs in O(n log h) time without prune and search.

CS 497 (Spring 2000) - Jeff Erickson (jeffe@cs.uiuc.edu) 03 Feb 2000