These questions were used for the ICS 261 component of the ICS phase II exam, May 2004. However, I think they may be too difficult for this purpose. So, while they may be useful as practice questions, please do not assume that future exam questions will be equally difficult.

(a) Describe an efficient data structure for the following problem: you are given as input a set S of n points in the x-y plane, and must handle queries that specify query values a and b and return any point (x,y) in S with y <= ax+b, if such a point exists. What is the space usage, preprocessing time, and query time of your data structure?

(b) Suppose that there exists a data structure D for problem (a) that solves the problem in space R(n), preprocessing time P(n), and query time Q(n). Now we must solve a slightly more difficult problem: for each query, we must find the point with the smallest x coordinate among all points (x,y) in S with y <= ax+b. Describe how to use data structure D as part of a layered data structure that solves this harder problem. Analyze the space usage, preprocessing time, and query time of your overall data structure in terms of P, Q, R, and n.