Encounter problem at different speed/start point algorithm design

Question

Riding jet skis is popular again, so let’s have a race! Unfortunately not all jet skis are equally fast, so to make the race more fair, the jet skis don’t all start at the same position (i.e., there’s no start line that all jet skis start from). You are the commentator and so you need to comment on which jet ski is in the lead. Formally, we are given n jet skis, traveling parallel to each other to avoid collisions (from left to right from your perspective). Each jet ski i travels at a constant speed vi. At time t = 0 the jet skis are at positions p1, ..., pn. We say that a jet ski is in the lead if its position is to the right of all other jet skis. Design an algorithm that computes the set of all jet skis that are in the lead at some point in time. For example, if we had 3 jet skis with speed 1, 2, and 3 and starting positions 10, 0, −1, your algorithm needs to report jet ski 1 (which is in the lead at time t = 0) and jet ski 3 (which is in the lead from t = 5.5). Your algorithm should not report jet ski 2, as this jet ski is never in the lead. As usual, also prove its correctness and analyze its running time. For simplicity you can assume that all pi and all vi are distinct and that at no point in time three jet skis are at exactly the same position.

I can't find an algorithm with time complexity better than O(n^2).

Answer 1

The location of each jet ski, starting at position p and travels at rate r, can be written as the function f(t) = p + r * t. These functions are lines.

You can use Convex Hull Trick or Li Chao Tree to efficiently maintain which of the lines gives the maximal value at arbitrary values of t. Without knowing the exact format of your output it is hard to say which is the best to use.

Answer 2

Here's an example with 4 jet skis. At time t = 0 each jet ski has a starting position (sp1 to sp4) and and velocity (v1 to v4). The distance d of each jet ski at time t is d(t) = sp + v * t.

The speed of each jet ski can be different, but is constant. We can also assume that the jet skis move forward (v > 0). The jet skis' distance over time can be drawn as a set of lines.

We want to compute at a given time t which jet ski is currently in lead and which jet skis were in lead before that. The jet ski in lead is the one with the greatest distance at that time.

Who is in lead at the start (t = 0)? That's easy: It's the jet ski with the greatest start distance. In my example the blue jet ski 4 with sp4.

Under which circumstances does a jet ski lose the lead to another jet ski? Mathematically, to overtake another jet ski, its line must intersect the other jet ski's line.

We have to compute the intersections of the blue line with all the other lines. If we have n lines, we have to compute the intersections of 1 line with the (n-1) other lines. We can even reduce the number of computations if we filter out all slower jet skis (lower v than the blue line). The jet ski 3 (orange) starts behind the jet ski 4 (blue) and has a slower speed. It can never overtake the blue one.

If we filter the slow jet skis out, we have to compute only two intersections in the first iteration:

We have to choose the intersection at the lowest time.

Now in the next iteration we can filter out:

• The blue line: Once overtaken, a jet ski can never take over the lead again.
• All jet skis that are slower than the current leading jet ski.

In our example we only have to compute the intersection of the current lead (red jet ski 2) with the remaining green jet ski 1.

In the end our leader hull curve will look like that:

Regarding the complexity with n jet skis:

• To compute the leader at start we have to compare n start positions.
• A race of n jet skis can have (n - 1) changes of the lead position.
• To compute the leader in each iteration i we have to compute (n - 1 - i) intersections at maximum. For each iteration we can remove the previous leader.
• If we also filter out in each iteration the jet skis that are slower than the current leader, we reduce the number of intersection computations even more than (n - 1 - i).