# 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

## 1 Answer

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.

• Another term occasionally used for this concept is the upper envelope of the set of lines (for instance, in the generalization of this question to arbitrary convex curves instead of just lines, which leads to the study of Davenport-Schinzel sequences). – Steven Stadnicki May 24 '12 at 22:53
• 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