Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

  1. 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.
  2. 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.
  3. 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.
share|cite|improve this question
Perhaps you should mention what (little) you remember about the solution you seek. – Aryabhata Jan 22 '11 at 19:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.