Graphics Reference
In-Depth Information
Proof.
See [BKOS97].
The discussion above can be combined to answer the question in Problem 1.
17.3.3 Corollary.
Let S be a set of n axis-parallel segments in the plane. If k of
these intersect an axis-parallel rectangle, 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).
So far we have only considered axis-parallel segments. What if our segments are
not parallel to the coordinate axes? We could solve this segment-window intersection
problem with a trick. Simply enclose these segments in axis-parallel rectangles, so
that they become one of the diagonals of the rectangle. We can now apply what we
know about axis-parallel rectangle intersections. If a rectangle intersection is found
we will have to check if the segment actually intersects the window. Unfortunately,
it is easy to construct examples where the rectangles intersect the window but the
segments do not, so that our solution is not very efficient. Getting a better solution to
this problem leads to our next data structure.
We return to an earlier query problem, Problem 2a. Let I = {[a
1
,b
1
],[a
2
,b
2
],...,
[a
n
,b
n
]} be a collection of intervals. We want to find those intervals that contain a
query point c. Let e
1
, e
2
,..., e
m
be the ordered list of
distinct
left and right endpoints
of the intervals in I. These points induce a partitioning of the real line into the fol-
lowing open and closed intervals:
(
)
[
]
(
)
[
]
(
)
[
]
(
)
-•
,
eeeee ee
,
,
,
,
,
,
,...,
e e ee e
mmmmm
,
,
,
,
,
+•
(17.1)
11112 22
-
1
Each of these intervals will be called an
elementary interval
. The reason for including
the closed intervals that contain a single endpoint is that one may want to distinguish
between a query point being an endpoint or in the interior of an interval.
The first step to finding an interval that contains the query point is to find the ele-
mentary interval to which it belongs. Therefore we build a balanced binary search tree
T whose leaves correspond to the intervals in the list (17.1). If
n
is a leaf node in T, let
E(
n
) denote its associated elementary interval. We could store all the intervals of I that
contain E(
n
) in a list at
n
, but the only problem with this is a big cost in storage since
the same intervals would potentially appear in many different lists because it might
contain many elementary intervals. A more efficient approach would be to store the
interval in a list at a node that is the root of that subtree of T whose leaves consist of
the elementary intervals contained in that interval. We cannot quite do that but we can
come close. We define a data structure S = S(I) that accomplishes this:
(1) Let T = T(S) be the balanced binary search tree T whose leaves correspond to
the intervals in (17.1). If
n
is a leaf node in T, then E(
n
) will denote its asso-
ciated elementary interval.
(2) If
n
is an interior node of T, then E(
n
) will denote the union of elementary
intervals that are the leaves of the subtree of T with root
n
.
(3) At each node
n
of T we store E(
n
) and the subset I(
n
) of intervals in I defined by
_
I
()
=Œ
()
Õ
n
{
a
I
E
n
a
and
E Parent
(
()
n
)
À
a
}
.
The subset I(
n
) will be called the
canonical subset
of the node
n
.
