Usage of a data structure

  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.