Graphics Reference
In-Depth Information
Figure 17.2.
The sets I
left
, I
mid
, and I
right
.
move right and report the interval with that endpoint until we find a left endpoint
which is larger than c. If c > c
mid
, then we start at the largest right endpoint and move
left and report the interval with that endpoint until we find a right endpoint which is
smaller than c. There is the case where c = c
mid
, but this can easily be handled in the
earlier two cases.
We are ready to describe a data structure that will match the algorithm we just
outlined. Construct a binary tree T = T(I) as follows:
(1) If I is empty, let T be the empty tree.
(2) Otherwise, using the notation above, T will consist of a root and a left and
right subtree, namely, T(I
left
) and T(I
right
), respectively. To the root node of T we asso-
ciate the value c
mid
(T) = c
mid
and two sorted lists L
left
(T) and L
right
(T), where L
left
(T)
is a copy of I
mid
sorted by the left endpoints of its intervals and L
right
(T) is a copy of
I
mid
sorted by the right endpoints.
Definition.
The data structure T(I) is called an
interval tree
.
Algorithm 17.3.1 shows how an interval tree is used for a query.
17.3.1 Theorem.
The interval tree associated to a set of n intervals uses O(n)
storage and has height O(log
2
n) . It can be built in time O(n log
2
n). If there are k
intervals which contain the query point, we can report them in time O(log
2
n + k).
Proof.
See [BKOS97]. To speed up finding the medians c
mid
one needs to sort the
whole list of endpoints once and for all.
This finishes Step 1 in the solution to Problem 2.
Step 2.
Given the collection of segments that intersect a given vertical line, select
those that intersect an interval in that line.
To carry out Step 2 we must modify our interval tree T. Let c ¥ [d,e] be the verti-
cal interval. At the moment the tree T is only concerned with the x-coordinates of
points. We must also look at the y-coordinates. The problem is that the lists L
left
(T)
and L
right
(T) are inadequate. What we need to do in the case of L
left
(T) is check if end-
points lie in the rectangle (-•,c] ¥ [d,e]. See Figure 17.3. In the case of L
right
(T) we
must check if endpoints lie in the rectangle [c,+•) ¥ [d,e]. But we saw in Section 17.2
