Graphics Reference
In-Depth Information
17.3
Interval and Segment Trees
We begin with the following problem:
Which of a collection of axis-parallel segments in
R
2
Problem 1.
intersect a given
rectangle (or “window”) [a,b] ¥ [c,d]?
Let us divide the segments into four classes:
(1) Those that are contained in the rectangle.
(2) Those that intersect the boundary of the rectangle only
once
.
(3) Those that intersect the boundary exactly
twice
.
(4) Those that contain an edge of the boundary.
The segments belonging to classes (1) and (2) have an endpoint in the rectangle and
can be found using our answer to Problem 2 in the last section with respect to the
question “Which of the 2n endpoints lie in the rectangle?” Range trees or fractional
cascading can be used to provide the answer. This leaves the edges belonging to classes
(3) and (4). We concentrate on the edges parallel to the x-axis. Those parallel to the
y-axis can be handled in a similar manner. It follows that all we have to do is deter-
mine which segments intersect the left vertical edge of the rectangle.
Which of a collection of segments in
R
2
Problem 2.
that are parallel to the x-axis
intersect a given vertical segment a ¥ [c,d]?
Problem 2 is solved in two steps.
Step 1.
Determine which of the segments intersect a given vertical
line
?
Solving Step 1 is really a one-dimensional problem.
Problem 2a.
Let I = {[a
1
,b
1
],[a
2
,b
2
],...,[a
n
,b
n
]} be a collection of intervals. Which
of those intervals contain the query point c?
Our approach to solving Problem 2a will be to use recursion. Let c
mid
denote the
median of the 2n endpoints of these intervals. We shall use c
mid
to express I as the
disjoint union of three sets I
left
, I
mid
, and I
right
and replace the question about which
intervals contain c with three questions. Define
I
left
= the set of intervals in I which lie entirely to the left of c
mid
,
I
mid
= the set of intervals in I which contain c
mid
, and
I
right
= the set of intervals in I which lie entirely to the right of c
mid
.
See Figure 17.2. The interesting set is I
mid
. When trying to determine which of its
intervals contain c we have extra information in the case of this set that speeds up
getting an answer. If c < c
mid
, then we only have to check the left endpoints of the
intervals because all the right endpoints are larger than c
mid
. Similarly, if c > c
mid
, then
we only have to check the right endpoints of the intervals because all the left end-
points are smaller than c
mid
. Therefore, let us store the left endpoints in increasing
order and the right endpoints in decreasing order. We can now easily determine the
intervals that contain c. If c < c
mid
, then we start at the smallest left endpoint and
