An eikonal equation (from Greek εἰκών, image[1][2]) is a non-linear first-order partial differential equation that is encountered in problems of wave propagation.
The term "eikonal" was first used in the context of geometric optics by Heinrich Bruns.
[5] However, the actual equation appears earlier in the seminal work of William Rowan Hamilton on geometric optics.
The solution to the eikonal equation can be interpreted as the minimal amount of time required to travel from
(Alternatively this can be posed as a minimal cost-to-exit by making the right-side
corresponds to a time-optimal control problem using Bellman's optimality principle and a Taylor expansion.
The physical meaning of the eikonal equation is related to the formula where
There is a similar equation for velocity potential in fluid flow and temperature in heat transfer.
The physical meaning of this equation in the electromagnetic example is that any charge in the region is pushed to move at right angles to the lines[clarification needed] of constant potential, and along lines of force determined by the field of the E vector and the sign of the charge.
The magnitude of these normal vectors is given by the square root of the relative permittivity.
The line of constant phase can be considered the edge of one of the advancing light waves (wavefront).
Several fast and efficient algorithms to solve the eikonal equation have been developed since the 1990s.
[10] These algorithms take advantage of the causality provided by the physical interpretation and typically discretize the domain using a mesh[11][12][13][14] or regular grid[15][16] and calculate the solution at each discretized point.
Eikonal solvers on triangulated surfaces were introduced by Kimmel and Sethian in 1998.
into a regular grid and "marches" the solution from "known" values to the undiscovered regions, precisely mirroring the logic of Dijkstra's algorithm.
A number of modifications can be prescribed to FMM since it is classified as a label-setting method.
[11][12][13][14] Label-correcting methods such as the Bellman–Ford algorithm can also be used to solve the discretized Eikonal equation also with numerous modifications allowed (e.g. "Small Labels First" [10][17] or "Large Labels Last" [10][18]).
Two-queue methods have also been developed[19] that are essentially a version of the Bellman-Ford algorithm except two queues are used with a threshold used to determine which queue a gridpoint should be assigned to based on local information.
Sweeping algorithms such as the fast sweeping method (FSM)[20] are highly efficient for solving Eikonal equations when the corresponding characteristic curves do not change direction very often.
Some improvements were introduced such as "locking" gridpoints[19] during a sweep if does not receive an update, but on highly refined grids and higher-dimensional spaces there is still a large overhead due to having to pass through every gridpoint.
[22] Hybrid methods have also been introduced that take advantage of FMM's efficiency with FSM's simplicity.
A first-order scheme to approximate the partial derivatives is where Due to the consistent, monotone, and causal properties of this discretization[10] it is easy to show that if
, a lower-dimensional update must be performed by assuming one of the partial derivatives is
case we can use a first-order scheme to approximate the partial derivatives.
yields: If the discriminant in the square root is negative, then a lower-dimensional update must be performed (i.e. one of the partial derivatives is
We could also solve the equation on a subset of this plane, or on a curved surface, with obvious modifications.
In geometric optics, the eikonal equation describes the phase fronts of waves.
In the geometrical optics case, this means that wavefronts cross.
follows from standard ODE theorems (using the non-characteristic hypothesis).
, which we have defined in a neighborhood of our initial plane, is the gradient of some function