Homework One. Due February 6 at the beginning of class. Late homeworks will not be accepted.

Problem 1: Given a convex polygon P, and a point w that is outside of P, we say that a point q on the boundary of P is visible to w if the open line segment wq does not intersect P. (the open line segment does not contain w or q, just all the points between them).
For this problem, suppose P is an n-sided convex polygon that is enclosed by a circular disk C. Our goal is to make an O(n) algorithm that determines if there exist two points w₁ and w₂ that are outside P, inside C, and together see every point on the boundary of P. If these points exist, we need to output such a pair of points.

To solve this problem, follow the following three steps:

(a) First, show that if two such points w₁, w₂ exist, then they may be assumed to be on the boundary.

(b) Explain how to subdivide the boundary of C into circular arc intervals such that all points within each interval "see" the same edges of P. Show that this can be done in O(n) time.

(c) Use (a) and (b) to present an O(n) time algorithm for this problem.

Problem 2: Suppose you are given a convex polygon P, with n vertices in counter-clockwise order (stored in an array). Show how the find the following in O(log n) time:

(a) Given a linear function f(x,y) = ax + by, find the vertex of P that minimizes the values of this function. (One function might be f(x,y)=0x+1y, in which case the point that minimizes the function is the lowest point of the polygon).

(b) Given a point w outside the polygon, find a tangent vector (a line through w that intersects only one point of the polygon).

Problem 3: A polygon P is star-shaped if there exists a point q inside the polygon such that for every point p in the polygon P, the line pq is contained within P. You are given the polygon P as a counterclockwise list of vertices. Give an O(n) algorithm to compute the convex hull of P. Prove the correctness of your algorithm -- (at least argue that every edge of your output is actually on the convex hull).

Problem 4 (hard): Given a path p₁,p₂,p₃,... p_n, that ALWAYS TURNS left, give an O(n) algorithm to determine if the path has any self intersections. (you may assume a constant time subroutine for checking if a pair of segments intersect).