[comp.theory] Solution to 2-D search problem

gautam@CS.WISC.EDU (Das Gautam) (12/24/87)

I am looking for solutions to the following 2-d search problem:

Given k points on a plane. A query specifies a triangle, with one side
parallel to the x axis. The output of the query should be the point
within the triangle with the largest y coordinate.

I am also interested in the "rectilinear version", where each query
specifies a rectangle, with its sides parallel to the axes.

I would like to see solutions which involve O(klogk) preprocessing time,
and O(logk) queryprocessing time. However any solution which involves
subquadratic preprocessing and sublinear queryprocessing would also be
useful.