Graphics Reference
In-Depth Information
Figure 17.5.
A slab.
cally, that is, a segment b will be above a segment a if and only if both endpoints of
b lie above L(a). If both segments lie in the same line, it does not matter which is con-
sidered above which. For example, the segments in Figure 17.5 are listed in decreas-
ing vertical order. These observations lead to the following data structure for solving
Problem 3:
(1) Create a segment tree S for the intervals that are the projections of the seg-
ments on the x-axis, but store the actual segments in the canonical subsets
rather than their projections.
(2) Maintain the canonical subsets I(
n
) at a node
n
as a binary search tree based
on the vertical order of the segments.
To make a query with respect to the vertical segment
q
, we search the segment tree
S. For each node
n
we encounter we do what amounts to a one-dimensional range query
on the canonical subsets with respect to the interval [c,d]. This approach gives us.
17.3.5 Theorem.
Let S be a set of n segments with disjoint interiors 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).
Proof.
See [BKOS97].
17.3.6 Corollary.
Let S be a set of n segments with disjoint interiors 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).
17.4
Box Intersections
As we have pointed out in the past, computing intersections is often a very expensive
operation and it would be better not to start such computations unless one was
