7.2.4 Do n Line Segments Intersect?Suppose now that we are given n straight-line segments on a plane with each segment specified by its two end points. An interesting question then is: Do any of these line segments intersect? The straightforward approach requires 0(n2) time: there are n(n - 1)/2 possible pairs of line segments which must be checked for intersections, and checking for the intersection of any given pair of line segments requires constant time. Once again, however, the most straightforward approach is not the most efficient one. We describe next an algorithm that requires 0(n log2 n) time [SHAM 76] to answer the problem: "Is there at least one intersection? If so, identify one." In the x-y coordinate system we shall call the left (right) end point of a given line segment that end point of the segment with the smaller (larger) value of the x-coordinate.6 Suppose now that we begin "sweeping" a vertical line along the x-axis (Figure 7.17). Two line segments S and T are then said to be comparable at x = x1 if they are both intersected by the vertical line at x = x1 The segments are consecutive if S is immediately above or immediately below T; in the former case we write S = above (T, x1), in the latter S = below (T, x1). Note that it is possible that no line segment will be above and/or below a line segment T for some or all values of x. The key observation leading to the algorithm below is that if two line segments S and T intersect for some value of x = x1, they must be consecutive7 for some range of x x1. The algorithm thus concentrates on those line segments which become consecutive for some range of values of x. The algorithm begins by sorting the 2n end points from left to right according to the values of their x-coordinates and then sweeps through the 2n end points from left to right. During the sweep, the algorithm maintains a list of current line segments which is sorted according to the order in which the line segments intersect the vertical sweep line. This sorted list is updated every time an end point is encountered: if the end point is a left end point, the corresponding line segment is added to the sorted list at the appropriate place; if it is a right end point, it is deleted from the list (see also Figure 7.18). The algorithm performs a check on whether two line segments intersect only when they become consecutive in the sorted list of line segments. It stops and returns the names of two intersecting line segments as soon as it finds an intersection. We can now present the details of the algorithm: Algorithm for the Intersection of Line Segments (Algorithm 7.1)
To prove that this algorithm works, (i.e., that it finds an intersection
if there is at least one), it is sufficient to show (see Problem 7.5)
that if the algorithm is not stopped when it finds its first
intersection, it is guaranteed to find eventually the leftmost
intersection of the line segments. This statement
emphasizes the fact that the first intersection discovered by Algorithm
7.1 is not necessarily the leftmost intersection. This peculiarity is
illustrated in Figure 7.19. Another peculiarity of Algorithm 7.1 is
that, if allowed to process all end points, it may "miss" some
intersections (see again Figure 7.19), although, as we just stated, it
will never miss the leftmost one.
What is the computational complexity of Algorithm 7.1 ? Step 1 requires
O(n log2 n) time for sorting the 2n end points. [It actually requires
0(2n log 2n), but remember that in the theory of computational
complexity 0(2n) is
equivalent to O(n).] The addition (or deletion) of line segments to (or
from) the sorted list of current line segments in Step 2 requires O(log2
n) time, since the sorted list can contain at most n line segments at
any time. Checking whether two line segments intersect requires constant
time (i.e., is independent of n). Since in the worse case, when there is
no intersection, Step 2 must
be repeated 2n times, Step 2 also consumes a total time which is O(n
log2 n). Noting that Step 3 is trivial and will be repeated 2n times in
the worst case, we thus conclude that Algorithm 7.1 is O(n log2 n), as
suggested initially.
|