- [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)** - The "three-penny algorithm" from Graham's scan computes the convex hull of some
simple polygons, but not all. Describe a simple polygon
- [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 p
_{1}, p_{2}, p_{3}, ..., such that for all n, the Voronoi region Vor(p_{n}, S_{n}) has n-1 edges. This is a worst-case input for any incremental Voronoi diagram algorithm. Here, S_{n}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.]

- [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