Ok, I've been playing with the "optimal" paths with acceleration vectors (At+B)/|At+B|, as described in the Corrozza, et al, paper. I've been trying to find an optimal "orbit" path around a square inscribed in the unit circle, where the acceleration vector a always has |a|=1. Here "orbit" means that the path goes around exactly once, hits every vertex, is continuous and its velocity vector is continuous. Although there is no requirement that the absolute value of the velocity vector at each vertex is the same, there doesn't appear to be any reason to doubt that a truly optimum path would have this property. If I take 4 segments of the type described in the paper, I can get very close to the circular path, both in space and in time, but I can't seem to be able to beat the circular path in terms of minimal time. The times are very close -- differing only by a percent or so, but they're still different; the path of the type given in the paper is always a bit slower than the circular path. It doesn't seem to help, whether the non-circular path goes outside the circular path or inside. Since the paper claims that its "optimal" paths are optimal, is the paper wrong? I don't know enough calculus of variations to be able to critique the paper. At 07:36 AM 12/8/2010, Henry Baker wrote:

Thanks very much, Andy, for the Mathematics Intelligencer reference. I found this description:

http://blog.sciencenews.org/view/generic/id/64589/title/Winning_the_World_Se...

Here's the full paper (basically Carroza's 2009 undergraduate thesis at Williams College):

Carroza, Davide; Johnson, Stewart; Morgan, Frank. "Baserunner's Optimal Path". Math. Intelligencer 32, 1 (2010), 10-15.

http://www.springerlink.com/content/t7q081384758kl5l/fulltext.pdf

--

The Carrozza, et al paper is quite relevant -- especially: --- Lemma 2.

A fastest C(1,1) path from one point to another in the plane, given initial velocity, final velocity, and a bound sigma>0 on the magnitude of the acceleration a,

a = sigma*(At+B)/|At+B|

for some constant vectors A, B, is unique. ---

The cool thing about this lemma is that the optimal paths are _catenaries_ in _velocity space_ !

---

There are obviously several potential variations on the problem:

1. A path that goes _through_ all the vertices versus a shortest path that goes completely around the triangle (it may be faster for some really slim triangles to not even attempt to touch one of the vertices, but you still don't cross the triangle boundary). My initial goal doesn't require going through all the vertices (so it isn't completely analogous to the "running bases" problem), so it is conceivable that a simple circular orbit with the largest triangle side as diameter may be the best solution (for some non-obtuse triangles).

2. The path is a true cyclic "orbit": the positions & velocities match seamlessly at the beginning & end. It is conceivable that the fastest such "orbit" may actually go around the triangle twice (or k times), in which case we take the total time & divide by k. I.e., it may not be necessary to match accelerations & velocities on a single pass, so long as we match them at some fixed integer number of passes. For example, an optimal path that starts with initial velocity 0 might get faster & faster on each trip around the triangle, but converge to an optimal cyclic path.

I guess that it is unlikely, but perhaps possible to have a optimal chaotic solution which _never_ matches, in which case we may have to look for a limit of the running average time. My model for this sort of chaotic behavior is the Minsky circle-drawing method from Hakmem.

3. Obvious extension to (convex) polygons -- e.g., base-running.

At 09:35 PM 12/7/2010, Andy Latto wrote:

...

On Tue, Dec 7, 2010 at 5:58 PM, Henry Baker <hbaker1@pipeline.com> wrote:

...

I'm still trying to solve for the optimum path around a triangle, subject to the acceleration constraint |a|<=1.

By "around a triangle", it seems you mean any path that passes through the three vertices of the triangle; is this correct?

Also, I think you have an additional implied constraint that the route be cyclic, that is, the velocity at the end of the path is the same as the velocity at the beginning. Otherwise the best solution for the degenerate triangle would be to start at one end of the line segment with velocity 2, decelerate until you reach the other end with velocity zero, and then continue to accelerate in the same direction until you return to the original vertex, again with speed 2, but now in the direction away from, rather than towards, the other vertex.

The Mathematical Intelligencer had an article a month or two back about the optimal way to run the bases in baseball. That is, the fastest path with bounded acceleration starting at one vertex of a square with velocity 0, passing through the other three vertices, and returning to the original vertex (though without the requirement that the final velocity be 0). I think much of this article is relevant to your triangle problem.

Andy