Multiple shooting approach for computing approximately shortest paths on convex polytopes

摘要

In this paper, we use a multiple shooting approach in solving boundary value problems for ODE to introduce a novel iterative algorithm for computing an approximate shortest path between two points on the surface of a convex polytope in 3D. Namely, the polytope is partitioned into subpolytopes, shooting points and a Straightness condition are established. The algorithm specifies how to combine shortest paths between shooting points in subpolytopes to become the required shortest path by the Straightness condition. In particular, the algorithm does not rely on Steiner points and graph tools on the entire polytope. It is implemented in C++ and a comparison with Agarwal, Har-Peled, and Karia’s algorithm, on the accurate construction of the shortest path, is presented.