Graphics Reference
In-Depth Information
procedure
SegmentTreeInsertion (
segment tree
S,
interval
a)
begin
if
E (S) Õa
then
Insert a into the set I (Root (S))
else
begin
if
E (Root (LeftSubtree (S))) «aπf
then
SegmentTreeInsertion (LeftSubtree (S), a);
if
E (Root (RightSubtree (S))) «aπf
then
SegmentTreeInsertion (RightSubtree (S), a);
end
end
;
Algorithm 17.3.3.
Segment tree insertion algorithm.
Proof.
See [BKOS97]. The key observation about the space requirement is that any
interval is stored in the interval list of at most two nodes per level and the height of
the tree is O(log
2
n).
In this section we have described two data structures, the interval tree and the
segment tree, both of which speed up queries about which intervals from a set of inter-
vals contain a given point. The interval tree uses only linear storage and is therefore
better for simple queries. On the other hand, the segment tree is better when we have in
mind more complicated queries, such as testing for intersections with a given window.
The reason is that the interval tree will inspect O(log
2
n) nodes in a query, but not all of
the intervals associated to those nodes will contain the query point. In a segment tree
search, our answer will consist of the union of each
entire
canonical subset of intervals
encountered at the nodes in our search. As an example of the advantage of the segment
tree we return to the non-axis-parallel segment intersection problem.
Problem 3.
Which of a collection of segments in
R
2
, not necessarily parallel to the
x-axis but not vertical, intersect a given vertical segment
q
= a ¥ [c,d]?
Consider the segment tree built from the x-coordinates of the segments. Alterna-
tively, we are talking about the segment tree built on the intervals on the x-axis that
are the orthogonal projection of the segments on that axis. We make one slight change
in that segment tree, in that we shall store the actual segments in the canonical
subsets, not their projections. Then when we encounter a node
n
of that tree in a
query for a, E(
n
) corresponds to a
slab
E(
n
) ¥
R
in the two-dimensional problem and
so the tree gives us information about which slabs are crossed by our original seg-
ments. See Figure 17.5. Furthermore, a segment a intersecting the line x = a will inter-
sect our vertical query segment
q
if and only if the top endpoint of
q
lies above the
line L(a) determined by a and the bottom endpoint lies below it. To find these seg-
ments, we make another assumption, namely, we assume that the interiors of all of
our segments are disjoint. With that assumption, one can order the segments verti-
