Shortest path in paragliding race

Question

I'm a paragliding pilot. A paragliding race is defined as a set of virtual buoys. The pilot who flies through all buoys first wins.

A buoy is defined with two parameters:

• the coordinates of a point
• a radius

This defines a cylinder in a 3D space, but for simplicity let's keep the problem in 2D. A race could look something like this (approximate drawing): A=1000m; B=3000m; C=2000m; D=500m

The pilot should start inside circle A, then fly inside circle B and C (or at least just 'touch' it) and should end inside circle D.

How do you calculate the optimal (shortest) path?

The result should be the coordinates of all segments that make part of the shortest path.

Answer 1

If the path is known a priori to be ABCD and only the exact points are unknown, then the total distance (squared) can be written as a function of 4 variables.

One parameterization of point i is of course

x(t_i) = x0_i + r_i * cos(t_i)
y(t_i) = y0_i + r_i * sin(t_i)

The path length squared is

D^2 = sum_{i = 1, n-1} (x(t_{i+i}) - x(t_i))^2 + (y(t_{i+i}) - y(t_i))^2

The four variables you're solving for are t_1,...t_4. After substitution, the final expression for D^2 is a pretty hairy quadratic over sine and cosine. You're out to minimize that quantity.

This is not something likely to admit an analytic solution.

You could also try a rational quadratic parameterization of the circle, but you'd end up with a rational quartic. Not much (any?) simpler.

Happily even such hairy functions can be minimized by standard numerical non-linear optimization algorithms such as (as someone suggested in comments) gradient descent.

In the general case, you can't guarantee that minimums found by such algorithms are global. But here it seems the solution space might be convex, at least for most problem instances, which makes a local minimum also global.

There's also likely to exist good heuristic ways of choosing starting points for the numerical iteration. For example take the path along the centers of the circles. For each circle pick the midpoint between its two intersections with the path.

With similar logic you can constrain the values of each t_i to a range always less than \pi.