Consider a matrix filled with some nodes containing positive integers ("starts"), some nodes marked as a wall, and the rest of the nodes given a value of infinity.
The propogation rule is simple: For each node, check if any of its 4 neighbors' values are greater than the current node's value plus one. If so, set their value to this node's value plus one. If that neighbor is a wall, don't modify it's value (walls are always infinity). Repeat until no more propagation occur.
Given $O(1)$ nodes, is it possible to compute their final propagation values in asymtotically less than $O(nm)$ time?
Edit:
Formally, consider the following simple rule for propagation: Given a matrix $M \in \mathbb{N}^{n\times m}$, and set of starts $S \subset \{(x, y, val) \in \mathbb{N}^3 | x<n, y<m\}$:
- Set all elements in the matrix to $\infty$, then $\forall s \in S, M(s_x, s_y) = s_{val}$. Assume WLOG that there aren't more than one $s \in S$ for each $(x, y)$.
- For every $(x, y)$ such that $M(x, y) \neq \infty$, set all surrounding nodes $M(x + 1, y)$, $M(x - 1, y)$, $M(x, y + 1)$, $M(x, y - 1)$ that have values greater than $M(x, y) + 1$ to $M(x, y) + 1$. (if that surrounding node is not in the matrix, ignore it)
- Repeat 2 until the grid is full and no more propagation can occur.
I am interested in computing the resulting value for $O(1)$ goal nodes in asymptotically less time then the $O(nm)$ time it takes to propagate outwards.
If there is only one start, call this start $s$, and the resulting $M(x,y)$ for any node can simply be found with the modified Manhattan distance $M(x,y)=|s_x−x|+|s_y−y|+s_{val}$ which takes $O(1)$ time.
If there is more than one start, $M(x,y)=\min\limits_{s \in S} |s_x−x|+|s_y−y|+s_{val}$, so the resulting $M(x, y)$ can be found in $O(|S|)$ time. This can be improved to $O(log(|S|))$ if $S$ are prepossessed into a quadtree beforehand, but this is only helpful is $|S|$ is less then our number of goal nodes.
That piece is trivial though. So next, consider if we augment the problem with walls that don't allow any propagation through them. Formally, walls $W \subset \{(x, y) \in \mathbb{N}^2 | x<n, y<m\}$ that don't allow their value to be modified in step 2.
With walls, is it possible to compute the value of any $O(1)$ goal nodes in asymptotically less than $O(nm)$ time?
