Suppose there are two unsorted arrays A and B, each consisting of n line segments. Each element belonging to A is a horizontal line segment with coordinates (0, a) and (a, b) for some 0 0. Each element belonging to B is a vertical line segment with coordinates (a’, 0) and (a’, b’) for some a’>0, 0
a) Prove that either the left-most vertical segment and the bottom-most horizontal segment intersect, or one of them does not intersect any segment.
b) Create a O(n) algorithm that checks if there exists at least one pair of intersecting line segments. Analyze the runtime and discuss the correctness of the algorithm.