Assume we have a data structure that supports the operations Insert(P, x), which inserts a point into P ,and NearNeighborr(P, q), with the following guarantees: 1. If there exists a string x in P such that dist(x, q) r, then NearNeighborr(P, q) will output some y P for which dist(y, q) Cr; 2. If every string x in P satisfies dist(x, q) Cr, then NearNeighborr(P, q) outputs Fail. Note that r is a parameter known to the data structure. Exercise 1. Assume that for any r {0, 1, . . . , d}, we can implement a data structure such that Insert and NearNeighborrrun in time T (n), and NearNeighborrsatisfies property 1. with probability at least 2/3, and property 2. with probability 1. Show that we can then implement a data structure that supports Insert and ApxNearestNeighbor(P, q) in time O(T (n) log d), so that ApxNearestNeighbor(P, q) achieves approximation factor 2C and success probability 2/3. Recall that ApxNearestNeighbor(P, q) is required to output some x P such that min{dist(x, q) : x P }dist(x, q) C min{dist(x, q) : x P },