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.


Fat nodes would be better. Path copying would require the whole queue to be copied after each enqueue operation, which would be too slow.


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.

In a Voronoi diagram, suppose that vertex v is on the boundary of the region for site p. Then there are at least two edges incident to v, because if there were only one edge it wouldn't separate the boundary from anything else. Suppose one of these edges is the boundary between the regions for site p and site q, and the second is the boundary between the regions for site p and site r. It is not possible for q to equal r, because two regions either have a boundary without vertices or they only generate a single edge at a boundary vertex. So v separates at least three regions altogether, and since there is an edge for each adjacent pair of regions in cyclic order around v, there are at least three edges. Therefore, the number of pairs (v,e) involving v is at least 3, and summing up over all choices of v we see that the total number of pairs, X, is at least 3V.

Every edge has at most two endpoints, so X <= 2E.

Putting these two inequalities together, 3V <= X <= 2E, so 3V <= 2E or equivalently 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.

Substitute 3V/2 for E in Euler's formula, giving
V - 3V/2 + n in place of V - E + n. Since we substituted a negative number with a smaller magnitude for a negative number with a larger magnitude, the value of the formula must increase: that is, V - 3V/2 + n >= 1.
Simplifying, n-1 >= V/2 and 2(n-1) >= V, so V = O(n).

Now, E = V + n - 1 = O(n) + n - 1 = O(n) as well.