What are the state-of-the-art algorithms for pathfinding on a continuous map of the Earth?
The deterministic requirement isn't all that constraining. That just implies your vehicle is certain of the state it's in. That being said, you'll probably want to plan paths in a way that allows you to avoid obstacles. The best way I've seen this done is with sampling-based planners. Steven LaValle wrote the central academic resource on this topic: Planning Algorithms. 

The RRT* algorithm is among the planners he describes. This algorithm generates the state space tree with random samples and a few heuristics to ensure feasibility (e.g. obstacle avoidance) and optimality. Details on RRT* can be found in LaValle's book, or at Sertac Karaman's website. The asymptotic time and memory characteristics are described as O(nlogn) to process, and O(n) for queries. The algorithm is linear, O(n), in space complexity too.