Causal Domain Restriction for Eikonal Equations
For researchers needing efficient solutions to continuous shortest path problems at specific points, this method offers a heuristic-based domain restriction that improves efficiency while maintaining accuracy.
The paper introduces a causal domain restriction method for solving continuous shortest path problems via eikonal equations, reducing computational work without sacrificing convergence under mesh refinement. It demonstrates advantages over previous techniques on 2D and 3D isotropic examples.
Many applications require efficient methods for solving continuous shortest path problems. Such paths can be viewed as characteristics of static Hamilton-Jacobi equations. Several fast numerical algorithms have been developed to solve such equations on the whole domain. In this paper we consider a somewhat different problem, where the solution is needed at one specific point, so we restrict the computations to a neighborhood of the characteristic. We explain how heuristic under/over-estimate functions can be used to obtain a causal domain restriction, significantly decreasing the computational work without sacrificing convergence under mesh refinement. The discussed techniques are inspired by an alternative version of the classical A* algorithm on graphs. We illustrate the advantages of our approach on continuous isotropic examples in 2D and 3D. We compare its efficiency and accuracy to previous domain restriction techniques. We also analyze the behavior of errors under the grid refinement and show how Lagrangian (Pontryagin's Maximum Principle-based) computations can be used to enhance our method.