|
7.5 Further work with Algorithm 7.1 Refer to Algorithm 7.1 which
examines a set of n line segments to find if at least one pair of them
intersect. a. Show that, if the algorithm is allowed to proceed after it discovers an intersection (if there are any), it will eventually discover the leftmost intersection in the set of line segments. b. Modify the algorithm so that, if allowed to process all n line segments, it will find all existing intersections. (As stated, Algorithm 7.1 may miss some intersections.) What is the computational complexity of the modified algorithm?
|