The problem is 10.6a from Computational Geometry: Algorithms and Applications.
We want to solve the following query problem: Given a set $S$ of $n$ disjoint line segments in the plane, determine those segments that intersect a vertical ray running from a point $(q_x, q_y)$ vertically upwards to infinity. Describe a data structure for this problem that uses $O(n \log n)$ storage and has a query time of $O(\log n + k)$, where $k$ is the number of reported answers.
It was a homework question to a CG course I was taking a year ago. I solve the problem, but I remember the solution was much more elegant. Now I can't find the solution sheet.
I hope someone can reconstruct the elegant solution.
Here I present basic idea of my solution:
- There exist a way to order the segments, so there are "higher" segments (segments $a$ is higher than segment $b$ another if there exist a vertical segment from $a$ to $b$, such that the higher intersection is on $a$). Number the segment from highest to lowest.
- Project all segments to $x$ axis. Create a interval tree. In the interval tree, instead of using 2 sorted list to contain the left end points and right end points, use 2 2D range tree instead.
- Each segment can be uniquely mapped into a pair $(x,y)$. It can be sorted by end point in $x$ direction, and the order we defined in $y$ direction. So we can query it with the 2D range tree. Using fractional cascading we can do it in $O(\log n+k)$ time.