arvind@utcsri.UUCP (Arvind Gupta) (01/06/88)
*** REPLACE THIS LINE WITH YOUR MESSAGE ***
Date: Wed, 23 Dec 87 17:40:45 CST
From: Das Gautam <gautam@cs.wisc.edu>
Subject: Solution to 2-D search problem
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.