The intended usage of a data structure is crucial to choose the most
ef ficient one. Hence, good general-purpose data structures minimize
assump tions about input characteristics. However, many times data
queries can be sped up significantly designing application-specific data
structures if input information is available.
Take for instance the segment intersection decision problem. That is,
given a set of segments, decide whether there exists in the set at least
one pair of segments that intersect. As we learned, we can solve this
problem using a sweeping technique that is common to
computational-geometry algorithms (Chapter 33.2). This algorithm runs in
O(n log n) time using Heapsort to sort the segments and a self-adjusting
BST to maintain the sweeping line status.
The implementation of the sweeping mentioned above is quite
efficient taking into account that finding all intersections is known to be in
Ω(n
2
). However, a natural question is whether it is possible to decide
intersection in o(n log n) using input information. For instance, the
sweeping algorithm studied assumes that all segments are available from
start (off-line). Thus, information such as maximum or minimum
coordinates of segment end points is easily computable in O(n). Then,
one could design an early-stopping algorithm that checks first if the range
of coordinates has the same order of magnitude as n, and if so decides
intersection using the sweeping algorithm with a o(n log n)
implementation, or otherwise use the standard O(n log n)
implementation.
The purpose of this assignment is to implement the described
strategy and compare efficiency experimentally drawing conclusions from
the results obtained. To simplify the task, we will assume that all endpoint
coordi nates are different and integer. Your task is the following.
1. (a) Implement the sweeping algorithm to decide inter section in a
set of segments following the pseudocode in Chapter 33. Sort
the segments using Heapsort (Section 6.4) and maintain the
sweeping status using a self-adjusting BST (e.g., RB trees
(Chapter 13)).
(b) Implement the sweeping algorithm to decide intersec tion in a
set of segments following the pseudocode in Chapter 33. Sort
the segments using Radix Sort (Section 8.3) and maintain the
sweeping status using a van Emde Boas tree (Chapter 20).
Given
4
that all coordinates are different, you can maintain the
sweep-line status using the y coordinate of the segment
endpoint as the key.
