Question

The intersection detection problem for a set S of n line
segments is to determine whether there exists a pair of
segments in S that intersect. Give a plane sweep algorithm that
solves the intersection detection problem in O(nlogn) time.
Prove it only requires O(nlogn) time.

Answer 1

Answer:-----------

Plane sweep algorithm:--------------

Intersect(S) :

1. Initially, we insert all of the endpoints of the line segments of S into the event queue. The initial sweep status is empty.
2. While the event queue is nonempty, extract the next event in the queue. There are three cases, depending on the type of event:

• Segment left endpoint: Insert this line segment into the sweep line status, based on the y coordinate of this endpoint and the y coordinates of the other segments currently along the sweep line. Test for intersections with the segment immediately above and below.
• Segment right endpoint: Delete this line segment from the sweep line status. For the entries immediately preceding and succeeding this entry, test them for intersections.
• Intersection point: Swap the two line segments in order along the sweep line. For the new upper segment, test it against its predecessor for an intersection. For the new lower segment, test it against its successor for an intersection.

Analysis: The work done by the algorithm is dominated by the time spent updating the various data structures (since otherwise we spend only constant time per sweep event). We need to count two things: the number of operations applied to each data structure and the amount of time needed to process each operation. For the sweep line status, there are at most n elements intersecting the sweep line at any time, and therefore the time needed to perform any single operation is O(log n), from standard results on balanced binary trees. Since we do not allow duplicate events to exist in the event queue, the total number of elements in the queue at any time is at most 2n + I. Since we use a balanced binary tree to store the event queue, each operation takes time at most logarithmic in the size of the queue, which is

O(log(2n + I)). Since I <= n² , this is at most

O(log(n²) ) = O(2 log n) = O(log n) time.