Optimal ship routing via Spherical Visibility Graphs

Improving the efficiency of maritime shipping has the potential to reduce carbon emissions and improve cost-effectiveness. The shortest collision-free path is a common baseline for ship routing applications, as distance travelled is related to the efficiency of a route. In 2-D, the shortest collision-free path is known to be contained on the so-called Visibility Graph. In this paper, we propose the Spherical Visibility Graph, and prove that the shortest collision-free paths on the surface of the sphere lie on the Spherical Visibility Graph. Additionally, we demonstrate that the edges of the Spherical Visibility Graph are only composed of minimal geodesics, halving the number of edges that need to be considered on the sphere. We provide a comparison of the Spherical Visibility Graph and a discrete grid to illustrate the differences between the two methods, as well as showcase the usefulness of the Spherical Visibility Graph for maritime navigation applications that require distance optimal trajectories.