Priority Search Tree

[Mohammad Hossein Rohban]

Hi,
There is a problem. We are given a number of intervals (all parallel to
x-axis) and each with a given y in x-y plane. We are given a rectangular
region specified by : (-infinity, x) * (y1, y2) and we want to find all
intervals intersecting this region (not overlapping, both low and high
points of desired intervals should not be in this region, only one of
them.)
Can we use a priority search tree (constructed on low end points of the
intervals) to solve this problem in O(lg(n) + k), where k is the number of
such intervals?

Regards,
Mohammad Hossein Rohban

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.