Computational Geometry Topics - Computer Graphics and Geometric Modeling - page 697

procedure 2dRangeQuery ( range tree R, real a, b, c, d)
begin
range tree splitR;

{ Except for the fact that we are dealing with range trees, the SplitNode function
below is just like the one in Algorithm 17.2.1. }
splitR := SplitNode (R, a, b);
if IsLeaf (splitR)
then check if we need to print point stored at splitR
else

begin
R := LeftSubtree (splitR);
while NotALeaf (R) do
if a £ x-value at root of R
then
begin
1dRangeQuery (T (Root (R)), c, d); {query on y}
R := LeftSubtree (R);

end
else R := RightSubtree (R); {query on y}
Check if we need to print point stored at R;

R := RightSubtree (splitR);
Do a similar traversal as we did for the left subtree, except that
we print leaves of left subtrees;

end

end ;

Algorithm 17.2.4. A 2d range query algorithm.

to be able to use our binary search trees, the only thing we really needed were linear
orders on what we called the “x-” and “y-coordinates” of points and any such would
do. The following lexicographic type ordering will do the job:

Interpret the phrase “the x-coordinate of (x,y) is less than the x-coordinate of
(x¢,y¢)” to mean x < x¢ or (x £ x¢ and y < y¢).
Interpret the phrase “the y-coordinate of (x,y) is less than the y-coordinate of
(x¢,y¢)” to mean y < y¢ or (y £ y¢ and x < x¢).

Another approach to solving Problem 2 is via Kd-trees. The query time using this
data structure is worse, namely, O( ÷ - + k), but it uses only O(n) space. Yet another
way is by using a technique called fractional cascading . In this case we use more space
but can get the query time down to O(log 2 n + k). See [BKOS97].