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

Algorithm 17.2.3 is a more precise description of how the range tree is built.
Algorithm 17.2.4 shows how a range tree is used to answer the query of Problem 2.
We summarize the results on Problem 2:

17.2.2 Theorem. Given a set of n points in R 2 , we can store them in a range tree
that can be constructed in time O(n log 2 n) using O(n log 2 n) space. Axis-parallel rec-
tangle queries can be made in time O(log 2 2 n + k), where k is number of points in our
set that satisfy the query.

Proof. For a proof see [BKOS97].

In the discussion leading up to Theorem 17.2.2, we implicitly assumed that all the
x-coordinates and y-coordinates are separately distinct. We shall now show that there
is a simple labeling trick that will enable us to drop this assumption. The fact is that

range tree function RangeTree ( point set P)
begin
binary tree T;
range tree R, R L , R R ;
real x mid ;

point set P L , P R ;

T := balanced binary search tree based on y-coordinates of points in P with points
also stored at leaves;
if |P| = 1
then R := range tree with only a root at which we store the single point of P
and to which we associate T

else

begin
x mid := median of x-coordinates of points in P;
P L := points of P with x-coordinates less than or equal to x mid ;
P R := points of P with x-coordinates larger than x mid ;
R L := RangeTree (P L );
R R := RangeTree (P R );
R := range tree with only a root at which we store x mid and
to which we associate T;
Make R L and R R the left and right subtree of R, respectively;
end ;

return R;
end ;

Algorithm 17.2.3. Building a range tree.