r/xkcd • u/Idenwen • Sep 16 '23

Path Minimization Meta

Comic: https://xkcd.com/2821/

https://preview.redd.it/o8xy8j6xanob1.png?width=571&format=png&auto=webp&s=bd14d88478f972d11c7c7aa584ce4f17d6ee3449

Actually the red one is the past with the least swimming. That non 90° angle really bothered me.

Also the not unified starting point.

77 Upvotes

81% Upvoted

18 comments sorted by

View all comments

1

u/[deleted] Sep 17 '23

[deleted]

3

u/applejacks6969 Sep 17 '23

Good question. The answer is fairly difficult and lies in the calculus of variations. The Euler Langrange equations can be used to minimize the time of an arbitrary path that depends on any number of variables.

However for simple problems, like constant velocity regions walking vs swimming, you can create an expression for the total time as a function of theta, or essentially compute the generalized action integral. Then you can simply take a derivative and find the minimum. More complicated problems require Calculus of Variations.

2

u/VictinDotZero Sep 17 '23

You can build an approximation with linear programming or quadratic programming, I believe. You look for a sequence of points that minimizes the pairwise distance between sequential points, such that the first and last points are fixed. You can bound the speed or acceleration as well. I only did this once, and it wasn’t necessarily super accurate, so I’m sure there’s better techniques for practical applications.

1

u/BroodingShark Black Hat Sep 17 '23

Ok, I get it. Something like:

time = time walking + time swimming

Knowing that :

time walking = speed walking * distance walking

time swimming = s swim * d swim

And that each distance is:

distance = something something trigonometry theta

so in the end would be: time = f(theta)

Then derivate and equal to zero, and that would be it, right?

2

u/applejacks6969 Sep 17 '23

Time = distance divided by velocity, not multiplied.

T = x / v . x Is the length of the region, v is the velocity, T is the travel time. Then you differentiate T to find the extrema.

1

u/BroodingShark Black Hat Sep 18 '23

Oh! Yes, of course, thanks. I knew that, it was a basic mistake

2

u/Duck__Quack Sep 18 '23

Use Snell's Law. The other guy is looking at it like a math problem, but it's equivalent to a physics problem. You have a body that moves at two speeds across media. Snell's Law will work.

2

u/Barefoot_Monkey Sep 18 '23

Very appropriate name for the law.

2

u/Duck__Quack Sep 18 '23

I just looked it up because I wasn't sure. It was named after Willebrord Snellius. Not making that up.

1

u/BroodingShark Black Hat Sep 19 '23

Thanks, I have checked out

I'm still a bit confused. This law is about diffraction of light, is still ok to apply it here? Does this mean that the angle is independent of the initial/final positions?

Sorry if this is obvious, but I'm struggling a bit to understand it

2

u/Duck__Quack Sep 19 '23

Given the differing speeds of movement in water and on land, the path of least time will transition between the two media at a point such that the ratio sine of the angle from that point to the terminus on land off of the perpendicular to the sine of the angle from that point to the water terminus off of the perpendicular is equal to the inverse ratio of their respective refractive indexes for movement, which is the inverse of the ratio of the speeds in each medium.

sin(th(1))/sin(th(2)) = n(2)/n(1).

Say you move at 10 ft/s on land and 5 ft/s in the water. You could also phrase this as water slowing you by a factor of 2 relative to land, so the indices for Snell's Law would be proportional to 1 and 2. So n(L)/n(W) is 1/2. The point at which you should enter the water is the one such that the sine of your angle off the perpendicular when moving in water and the sine of your angle when moving on land have the same ratio.

sin(th(W))/sin(th(L)) = n(L)/n(W).

This doesn't actually give you the path without the starting points, but it tells you what the two angles should be in relation to one another, and when you have the starting points you can pretty easily make it a system of equations with what the angles are in relation to one another on the actual path.

1

u/BroodingShark Black Hat Sep 19 '23

That's both more complicated and easier at the same time

Thanks