Priority Search Tree

Mohammad Hossein Rohban rahban at
Wed Jan 14 11:56:53 PST 2004

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
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?

Mohammad Hossein Rohban

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list