Graphics Reference
In-Depth Information
Figure 17.3.
Checking endpoints of L
left
(T).
procedure
IntervalTreeQuery (
interval tree
T,
real
c)
begin
if
NotALeaf (T)
then
if
c < c
mid
(T)
then
begin
Beginning with the leftmost interval in L
left
(T) move right
reporting all intervals that contain c and stop at the first
interval that does not;
IntervalTreeQuery (LeftSubtree (T),c);
end
else
begin
Beginning with the rightmost interval in L
right
(T) move left
reporting all intervals that contain c and stop at the first
interval that does not;
IntervalTreeQuery (RightSubtree (T),c);
end
end
;
Algorithm 17.3.1.
The interval tree query algorithm.
that a range tree is a good data structure for that. Therefore, we replace the lists L
left
(T)
and L
right
(T) in T with range trees R
left
(T) and R
right
(T) determined from the left and
right endpoints of I
mid
, respectively. The only change that has to be made in Algorithm
17.3.1 for querying an interval tree is that instead of traversing the lists L
left
(T) and
L
right
(T) we make queries on the corresponding range tree.
Summarizing, we get
17.3.2 Theorem.
Let S be a set of n horizontal segments in the plane. If k of these
intersect a vertical segment, then they can be reported in time O(log
2
2
n + k) using a
data structure that uses O(n log
2
n) space and which can be built in time O(n log
2
n).
