1. A queue (that is, a structure that handles enqueue and dequeue requests, and that dequeues items in the same order that they were enqueued) may be implemented as a singly-linked list of nodes that each have a value and a next pointer, with global pointers F and L to the first and the last item in the list. The queue operations may be implemented in constant time, as follows.

def enqueue(x):
    if L == null:
        F = L = new node with value x
    else:
        L.next = new node with value x
        L = L.next

def dequeue(x):
    result = F.value
    F = F.next
    return result

Which of the two persistence techniques described in class, the path copying technique or the fat node technique, would be more appropriate for making this structure persistent? Explain your answer.


2. Recall that in the lecture we defined the Voronoi diagram of a set of n point sites in the plane to be the partition of the plane into n convex polygonal regions such that the region for a site p is the set of points closer to p than to any other of the sites. We showed how to use persistent binary search trees to solve point location queries in the Voronoi diagram, and therefore to solve closest point queries for the original set of sites. But our analysis of the point location data structure was in terms of the number of vertices and edges in the Voronoi diagram, which is not necessarily the same as n.

(a) Suppose that the Voronoi diagram has V vertices and E edges. Let X be the number of different pairs (v,e) of a vertex v and an edge e that are adjacent to each other. Show that X >= 3V and X <= 2E (X might not be equal to 2E because some edges of the diagram may be infinite rays with only one endpoint). Conclude from these two facts that E >= 3V/2.

(b) For a graph drawn without crossings in the plane with V vertices, E edges, and F faces, Euler's formula is the equation V-E+F=2. Because of the infinite rays in a Voronoi diagram, the formula needs to be slightly adjusted: in this case, V-E+F=1, and F=n because there is one face for each input site. Combine the final inequality from part (a) with this adjusted version of Euler's formula to prove that V=O(n) and E=O(n). You do not need to prove that Euler's formula is true.