Path: utzoo!utgpu!utcsri!arvind
From: arvind@utcsri.UUCP (Arvind Gupta)
Newsgroups: ut.theory
Subject: THEORY NET: Solution to 2-D search problems
Message-ID: <5768@utcsri.UUCP>
Date: 6 Jan 88 15:03:15 GMT
Article-I.D.: utcsri.5768
Posted: Wed Jan  6 10:03:15 1988
Distribution: ut
Organization: CSRI, University of Toronto
Lines: 19

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