block by 1wheel 79ed32828a2db39ec232


Full Screen

Let S be a set of n disjoint line segments whose upper endpoints lie on the line y = 1 and whose lower endpoints lie on the line y = 0. These segments partition the horizontal strip [−∞ : ∞] × [0 : 1] into n + 1 regions. Give an O(nlogn) time algorithm to build a binary search tree on the segments in S such that the region containing a query point can be determined in O(log n) time. Also describe the query algorithm in detail.