Suppose I have got a solar-powered autonomous surface vessel somewhere in the fjords of Norway, supplied with a fairly recent set of maps, a GPS receiver, and no means of downlinking detailed commands from me. This vessel has to reach, say, the island of Hainan at the earliest possible moment.
- What are the deterministic algorithms for finding a maritime route on a globe?
What is their time and memory complexity?
Can I, for instance, use A* after transforming the map of the globe into a diagram with connected polygons (i.e. Delaunay triangulation on a sphere/ellipsoid) and what are other feasible approaches?
Answers should ideally provide references to papers with discussion of the above-mentioned questions.
As pointed out by Rob Lang, the algorithms must fit the usual criteria: in the absence of time constraints, lead to the shortest path between any two points on Earth's oceans and seas, or indicate pathfinding failure otherwise.
There are interesting sub-topics here (trading pre-computation time/storage for online computations, providing slightly suboptimal routes before a deadline kicks in etc.), but these are ancillary to the main issue.