Homework Problems
- [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.
- [January 20] A simple polygon is a circular sequence of line segments joined
end-to-end with no other intersections.
- 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.
- 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)
- [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.
- [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?
- [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.
- [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
- [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