In this problem we will investigate the properties of a variant of the Voronoi diagram, in which we replace the notion of nearest with farthest. Given a set P = {p₁, p₂, . . . , p_n} of point sites and site p_i P, recall that we defined Vor(p_i) to be the set of all points in the plane that are strictly closer to pi than to any other site of P. Define Far(p_i) to be the set of all points in the plane that are strictly farther from p_i than from any other site of P. As we did with Voronoi diagrams, we define the farthest-point Voronoi diagram to be the union of the boundaries of Far(p_i) for all points in P. Let NVD(P) denote the nearest-point Voronoi diagram of P and let FVD(P) denote the farthest-point Voronoi diagram of P.

1. Show that Far(p_i) is a convex polygon (possibly unbounded).

2. Unlike the nearest-point Voronoi diagram, a site may not contribute a region to the farthest point diagram. Show that Far(p_i) is nonempty if and only if p_i is a vertex of the convex hull of P. (Hint: Recall that a site p_i is on the boundary of Ps convex hull if and only if there is a halfplane containing P whose boundary line passes through p_i .)

3. Draw a picture of three points in the plane. Show (in different colors) NVD(P) and FVD(P). Label each region according to which sites are closest and farthest.

4. Repeat (c), but this time with four points, such that only three of the four points are on the convex hull.

5. Repeat (d), but this time with all four points on the convex hull. (Try to avoid degeneracies, such as four co-circular points or parallel sides.)

Please write the algorithm, a justification of its correctness, and a derivation of its running time. Write clear and convincing PSEUDO-CODE for your algorithm. NO CODE.