Graphics Reference
In-Depth Information
In the next section our object will be to describe quick intersection algorithms for
axis-parallel line segments, rectangles, and blocks (the axis-parallel one-, two-, and
three-dimensional boxes, respectively). Right now we concentrate on the problem of
determining which points (0-dimensional boxes) from a collection of points fall into
an axis parallel box.
Problem 1.
Assume that
S
= {r
1
,r
2
,...,r
n
} is a
fixed
set of n real numbers. Given
numbers a and b, which of the r
i
lies in the segment [a,b]?
If the question in Problem 1 is only asked once, then there is a straightforward
O(2n) solution. We simply compare each of the r
i
with the endpoints of the segment
[a,b]. However, if the question is asked many times with different segments, then it
turns out that we can do better.
Step 1.
We first build a balanced binary search tree T from the r
i
. (For the discus-
sion here, the term “balanced” means that all the leaves of the tree lie on adjacent
levels.) To do this we sort the numbers in
S
, put the median M of the numbers in
S
at the root of T, put the median of all the numbers in
S
that are less than M at the
root of the left subtree of T, put the median of all the numbers in
S
that are larger
than M at the root of the right subtree of T, and so on. The actual numbers are stored
at the leaves, but we use the values at the interior nodes to guide the search. See
Figure 17.1.
Step 2.
Search for a in T. Assume that the search ends at the leaf
n
a
. Search for b
in T. Assume that the search ends at the leaf
n
b
. The numbers of
S
that lie in [a,b] are
the leaves of T between nodes
n
a
and
n
b
. For example, Figure 17.1 shows the case
[a,b] = [25,72]. The leaves corresponding to the numbers that lie in the interval are
shown as black rectangles.
Figure 17.1.
Range searching with balanced binary search trees.
