# Determining position at some point in time

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.

• Forgive my ignorance, but if you have the current time can't you just do $d=v*t+k$, loop through the trains one by one, and keep track of the farthest? That would be $O(n)$ if I understand the problem correctly. Or do they specifically want $O(n\log n)$? It seems that fundamentally you're sorting an array of tuples $(train_n, v_nt+k_n)$ by their second element. – Robert Mastragostino May 24 '12 at 4:39
• @Robert: For the question to be interesting it probably means that the desired output is a list of indices $i$ such that train $\#i$ was leading at some instant of time $t_i\in[0,\infty)$. – Jyrki Lahtonen May 24 '12 at 5:44
• Hint: This should have the computational-geometry tag. – JeffE May 24 '12 at 8:08
• If you view the train positions as lines in $t-v$ space, the region to the right of all lines is convex. You are looking for all trains that contribute a segment to the boundary. Maybe you can adapt one of the convex hull algorithms. – Ross Millikan May 24 '12 at 8:17
• @RossMillikan, Thank you for the comment. Let's say I almost get the idea. But could you please elaborate a little more please, I don't understand how to represent a position. – com May 24 '12 at 18:20

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.
• Thank you Ross Millikan, so $x$ it's a positions of the train, on $y$ it's a time. Therefore the task is to find the rightmost train on the given time, which can be done by sorting in $O(nlogn)$. – com May 25 '12 at 4:40
• @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)$ – Ross Millikan May 25 '12 at 11:00