The Fast Marching Method, Fast Iterative Method, and Fast Sweeping Method are three ways of solving the Eikonal Equation on a discrete grid, essentially just a wavefront spreading out from initial points, e.g.:
The idea is that we want to compute the time $T(x, y)$ at which a wavefront, moving across a field with a velocity function $F(x, y)$, reaches each point in a grid, e.g.:
Where walls and such would be represented with $F(x, y)=\epsilon$ for some very small $\epsilon$.
This is good and these methods work very well in practice, however they all apply to fixed size grids.
In many applications, it is better to represent the speed field with some sort of tree, say a quadtree or octree. Areas with a larger tree cell representing them would simply then all have the same speed, though some sort of interpolation may even be possible. This can be interpreted by saying that we desire "higher resolution" results in some areas with a higher tree density, and "lower resolution" results in some areas with a lower tree density. Either way, is it possible to apply these methods (or methods like them) for solving $T(x, y)$ using a speed field $F(x, y)$ represented with some kind of a tree?
Trivially, I know you could simply find the "lowest resolution" of your tree - IE the smallest cell - then transform each larger cell into these smaller cells as the algorithm runs over them, but this seems far less than optimal, and kinda defeats the point of a tree in the first place. Thus, is there a better way to do this?
It seems pretty clear that the goal would be to have a $T(x, y)$ field that is also represented in the same kind of tree that $F(x, y)$ is represented in, to give similar density results, however I don't know if that's the best way to think about it either. More specifically $T(x, y)$ would probably end up being some kind of form where inner points (if we were trying to recreate the fixed-size discrete grid) are interpolations between the corners of the tree grid, but this is also essentially what it's doing anyway in order to map a discrete grid answer to a continuous one, so I don't feel like that's too big of a concern.
Really, this question was just motivated because current implementations of an Eikonal Equation solver are slow, for two reasons:
The dependencies each grid cell has on its neighbor's results. Something like the Fast Iterative Method makes them essentially less "tied together" so some level of parallelization is possible, but I'm wondering if there would be some way to further split up the work into independent grid cells that possibly derive results dependent on their neighbor values which will eventually be computed. This is sort of a side-note but I feel like the tree aspect may be tied into it due to how "low density" results would have to be smoothly approximated by "higher density" neighbors. This gets into point two:
The current methods compute the same accuracy for all points in the grid. In many situations good accuracy is only needed for specific portions of the map, so it would be nice if it were possible to "split up" the work into sections of desired high resolution results and sections of desired low resolution results. Doing that using some kind of a tree doesn't seem that straightforward with the current methods of solving this equation though.
