Solution to 2-D search problem

Article View: comp.theory

Article #1949

#1949

From: Das Gautam
Date: Wed, 23 Dec 1987 23:40

13 lines
1102 bytes

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.

Technical Details

Message-ID: <8712250019.AA23281@jade.berkeley.edu>

Path: arc1-ca.pugleaf.net!utzoo!utgpu!water!watmath!clyde!rutgers!sdcsvax!ucbvax!CS.WISC.EDU!gautam

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!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