Direction weighted shortest path planning
Jürgen Sellen · 2002
We examine shortest path planning under a direction weighted Euclidean metric, motivated by the problem of finding optimal routes for sailboats. We show that for piecewise linear weight functions the shortest path in the unrestricted plane always consists of 2 line segments, and by this solve the problem in a polygonal environment with a visibility graph approach. We then investigate the problem in a general setting, in which the weighted distance measure is supplemented by a link distance measure, and present polynomial approximation algorithms for this case.