Traversing Line Segments

Question

I have a question on this algorithmic problem; I'll paste the problem then go over my current thoughts and solution.

There are N (up to 100,000) line segments defined as [(x1, y1), (x2, y2)], where x1 < x2 and y1 < y2 (e.g. The line segments have positive slope). No line segments touch or intersect, even at endpoints. The first segment has (x1, y1) = (0, 0). Imagine each segment as a 2-D hill a person has to climb.

A person starts at (0, 0) and lands on the first hill. Whenever a person lands on a hill, he climbs to the end, which is (x2, y2) and jumps straight down. If he lands on another hill (anywhere on the segment), the process continues: he climbs that hill and jumps. If there are no more hills, he falls to -INFINITY and the process is over. Each hill (x1, y1) -> (x2, y2) should be regarded as containing the point (x1, y1) but not containing the point (x2, y2), so that the person will land on the hill if he falls on it from above at a position with x = x1, but he will not land on the hill if he falls on it from above at x = x2.

The objective is to count how many hills he touches.

My current thoughts

I'm thinking of sweeping a line across the plane along the x-axis. Each segment consists of a BEGIN and END event; everytime we encounter the beginning of a line segment, we add it into a set. Every time we encounter the ending of a line segment, we remove it from the set. And when we hit the END point of the current hill we are on, we should check the set for the highest hill that we can land on. However, I don't know how to determine how to check this quickly, because there could be potentially N entries inside the set. Also, after jumping on to another hill, the order of these will change because the slopes of each segment are probably different, and I don't know how to account for this difference.

Any thoughts?

Answer 1

In pre-processing you can traverse all segments and add points in an stl multimap< pair, linesegment> or something similar. Cost of this pre-processing would be O(NlogN). Then you can continue with your sweep line method. You need iterate points from multimap. Because all points are sorted, and contains reference to line the point corresponds to, it would cost O(N).