1. A polygon P is said to be "star-shaped" if it is possible to add one more point in its interior that can see all points of P by lines of visibility that stay within P -- see http://en.wikipedia.org/wiki/Star-shaped_polygon
If P is star-shaped, and v is a point inside P that can see all of P, then connecting v to all of the vertices of P forms a triangulation of P. Given a triangulation T of this type, define a(T) to be the minimum area of any of the triangles of T, and suppose that we wish to find the position of v that maximizes a(T). Describe how to formulate this as a linear programming problem.


2. In order to implement Seidel's linear programming algorithm, we need to find a permutation of a set of elements that is uniformly distributed over all permutations. Does the following algorithm correctly find a uniformly random permutation of an input array A[0]...A[n-1]? Why or why not?

def permute(A,n):
    for i in 0, 1, ... n-1:
        j = a random integer, uniformly distributed from 0 to n-1
        swap(A[i],A[j])
    return A


3. The diameter of a set of n points in the plane is the maximum distance between any two of the points. Is the problem of determining the diameter LP-type (http://en.wikipedia.org/wiki/LP-type_problem)? If so, prove that it satisfies the locality and monotonicity properties of LP-type problems. If not, explain which of these properties it violates, and provide an example that shows the property being violated.