Before revision:  To obtain our results, we introduce new techniques and ideas, including a reduction to a new geometric line segment selection together with an efficient solution .
After revision:  To obtain our results, we introduce new techniques and ideas, including a reduction to a segment selection query returns the jth smallest segment (the segment with the jth smallest y-coordinate) among the segments crossing the vertical line through x-coordinate i. The segment selection problem is to preprocess a set of horizontal line segments into a compact data structure that supports fast segment selection queries. We present a solution that uses O(n) space and support segment selection queries in O(\log n/ \log \log n) time, where n is the number of segments. Furthermore, we prove that that this query time is also optimal for any solution using near-linear space .