(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.