CS 164/266, Fall 2023, Practice Problem Set 7

1. Draw a kD-tree for the 15 points with coordinates \((i,i)\) for \(i=1,2,\dots,15)\)

2. Consider an approximate range query for a range with diameter \(d\), and approximation parameter \(\varepsilon\). The “query analysis lemma” slide of the lecture notes explains why a quadtree square that crosses the range (according to the definition on the slide has a lower bound of \(d/\sqrt 2\) on its side length. Give an argument proving that there is also an upper bound on the side length of a quadtree square that crosses the range.

   (It is ok for your answer to produce an inaccurate bound, as long as the bound is valid. If it helps you may assume that the range is a circle, but it should be possible to answer this question without making that assumption. Hint: assume you have a large square that crosses the range, find one of its child squares that contains a point of the inner boundary of the range, and use the assumption that this child does not cross the range to find a limit on how large it can be.)

3. Suppose we construct the onion layers of a point set by the following algorithm (which is not the fastest known method for the problem):

   • Sort the points by their \(x\)-coordinates, using an \(O(n\log n)\) time comparison sorting algorithm.
   • While the point set is non-empty, use Graham scan to find the outermost remaining layer (the convex hull of the remaining points), and remove those points from the set, keeping the remaining points in sorted order.

   What is the total time of this algorithm, using \(O\)-notation as a function of n?

4. Suppose that you wish to perform a binary search for a query number \(q\), in a data set consisting of \(k\) non-empty sets of numbers, having n total items (without any repeated numbers). As we saw in the lecture, fractional cascading allows this to be solved in total time \(O(k+\log n)\). But suppose instead that we just do a binary search in each set, in time \(O(log |S_i|)\) time for set \(S_i\).

   1. Suppose that the \(n\) items are distributed into sets in a way that minimizes the total time (the sum of \(log |S_i|\) for all \(i\)). How should they be distributed to achieve this, and what is the \(O\)-notation for the sum in terms of \(n\) and \(k\)?

   2. Suppose that the \(n\) items are distributed into sets in a way that maximizes the total time (the sum of \(log |S_i|\) for all \(i\)). How should they be distributed to achieve this, and what is the \(O\)-notation for the sum in terms of \(n\) and \(k\)?