How to find when the object changed its direction of motion

Question

Problem:

1. A ball is thrown up after sometime it loses momentum and starts falling back
2. A car moving in direction x and taking a U-turn & starts returning
3. A planet moving prograde and becomes retrograde at some point of time

We have:

• readings of the object position taken at regular intervals. (example below)

| datetime            | position | direction               |
|---------------------|----------|-------------------------|
| .......             | ..       | ...                     |
| 2024-02-10 10:00:00 | 15       | ..                      |
| 2024-02-11 10:00:00 | 17       | forward (17 - 15 = 2)   |
| 2024-02-12 10:00:00 | 20       | forward (20 - 17 = 3)   |
| 2024-02-13 10:00:00 | 21       | forward (21 - 20 = 1)   |
| 2024-02-14 10:00:00 | 22       | forward (22 - 21 = 1)   |
| 2024-02-15 10:00:00 | 21       | backward (21 - 22 = -1) |
| 2024-02-16 10:00:00 | 19       | backward (19 - 21 = -2) |
| .....               | ..       | ..                      |

• a function which gives us the position of the object at a given point of time position(datetime)

    func position(datetime){
        return position
    }

from the example readings above we subtract a position with the previous position and ascertain whether the object is still moving in the same direction or has changed direction. ie. somewhere between 14th and 15th object changes its direction of movement since the 21 - 22 = -1.

We have to find the exact time when object changed direction.
what do you suggest is the optimum way to find the time?
anything other than checking for every minute or second because position() is computationally expensive

I tried using the binary search by checking the mid point and moving either left or right bounds based on it. but it still wont work because after t0 object could still be moving in same direction.

I am sorry for the formatting of the question. I can't post the exact problem here. so I have used a few examples with similar cases. feel free to ask for more clarification

Answer 1

Optimum is function dependent.

Still the idea is this. You want to consider 3 points, low, mid, and high. You know their positions. You know that position_mid >= max(position_low, position_high).

By some means you will pick choose that is either between low and mid, or between mid and high. You then narrow in on this logic:

try_choice(low, low_position, mid, mid_position, high, high_position, choose):
    choose_position = position(choose)
    if choose < mid:
        if choose_position <= position_mid:
            return (choose, choose_position, mid, mid_position, high, high_position)
        elif low_position <= choose_position:
            return (low, low_position, choose, choose_position, mid, mid_position)
        else:
            # it looks like we were falling at low, let's find the peak from choose to high
            return (choose, choose_position, mid, mid_position, high, high_position)
    else:
        if choose_position <= position_mid:
            return (low, low_position, mid, mid_position, choose, choose_position)
        elif high_position <= choose_position:
            return (low, low_position, choose, mid, mid_position, choose, choose_position)
        else:
            # it looks like we were falling at high, let's find the peak from low to choose
            return (low, low_position, mid, mid_position, choose, choose_position)

Now how do we choose our answer?

One option is we take the midpoint of the wider interval, (low, mid) or (mid, high). This always allows us to get rid of at least 1/4 of the range. And so the range is narrowing by a constant factor each time, and the overall required number of steps is logarithmic in the precision we want.

Another option is that we plot a quadratic from the three points we have, and try to guess where the peak will be. If we're already close to a solution, this is going to be massively better than our existing points.

And yet another option is to look at where the peak should be, and then go just a little bit past it. To not just guess where we think the peak is, but to try to be sure of trapping it in a smaller range.

For an optimal algorithm, I think that you can use all three approaches. With logic that might look something like this 1-2 guesses logic:

generate candidate from quadratic fit
if the candidate is in the smaller of the two intervals:
    try candidate
        if candidate didn't wind up as midpoint:
            then try splitting larger interval
else:
    if candidate is < 1/3 from mid as the end:
        try just a bit past the candidate away from the mid
        if that did not wind up as end:
            then try splitting larger interval
    else:
        just split the larger interval

With the idea that we're never going to be worse than logarithmic in the precision, but we'll sometimes be a lot better.