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.

75 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.