Path: utzoo!utgpu!water!watmath!clyde!rutgers!sdcsvax!ucbvax!CS.WISC.EDU!gautam
From: gautam@CS.WISC.EDU (Das Gautam)
Newsgroups: comp.theory
Subject: Solution to 2-D search problem
Message-ID: <8712250019.AA23281@jade.berkeley.edu>
Date: 23 Dec 87 23:40:45 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: TheoryNet List <THEORYNT%NDSUVM1.bitnet@jade.berkeley.edu>,
        Das Gautam <gautam@cs.wisc.edu>
Distribution: inet
Organization: The ARPA Internet
Lines: 13

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.