3
$\begingroup$

I try to solve the following problem.

On $n$ parallel railway tracks $n$ trains are going with constant speeds $v_1$, $v_2$, . . . , $v_n$. At time $t$ = 0 the trains are at positions $k_1$, $k_2$, . . . , $k_n$. Give an $O(n\log n)$ time algorithm that detects all trains that at some moment in time are leading.

The problem is I don't know how to approach the above problem. I assume it's should very popular problem in computational geometry. I saw it few times before, but never considered to solve it.

It looks like that the problem assumes preprocessing the data before giving input the moment of time.

Complexity $O(n\log n)$ points out to process similar to sorting.

  • 0
    @RossMillikan, Thank you for the comment. Let's say I almost get the idea. But could you $p$lease elaborate a little more $p$lease, I don't understand how to represent a position.2012-05-24

1 Answers 1

2

Follow-up on my comment, long for another: For any given train, the position at time $t$ is $v_it+x_{i0}$ where $v_i$ is the velocity of train $i$ and $x_i0$ is its position at $t=0$. This defines a line in the plane. The set of all lines defines a region to the left where at a given time there is at least one train to the right and a region to the right were there is no train to the right. The rightward region is convex. A train is rightmost precisely when its line is the boundary. For example, if train 1 starts at 0 with speed 1 and train 2 starts at -1 with speed 2, they meet at (1,1). Train $1$ is rightmost before $t=1$, and train $2$ is after $t=1$. If train 3 starts at -2 with speed $3/2$, it is never rightmost. If you plot the three lines you can see that. This forms the basis of my statement that you want a convex hull of the right region.

  • 0
    @fog: In you original post, it seemed you were to find a list of trains that were rightmost at any time, a different problem. You are right that at a given time you can calculate each train position in $O(n)$, then sort in $O(n\log n)$2012-05-25