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?


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\}$:

  1. 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)$.
  2. 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)
  3. 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?

  • $\begingroup$ I don't see why walls make much difference; shouldn't we just replace $Min(|s_x - x| + |s_y - y| + s_{val})$ with $Min(dist(s,(x,y)) + s_{val})$ where $dist$ is the length of the shortest path on the graph? Computing the length of a shortest path is easy, albeit not constant time. And in there is probably a good algorithm that finds the shortest path from $(x,y)$ to all $s$ simultaneously. Is this not fast enough? $\endgroup$
    – usul
    Commented Jun 28, 2014 at 19:28
  • $\begingroup$ It is fast, but still dependent on the size of the graph, which isn't ideal. Even something that is dependent on the number of walls would be better, because then for $O(\sqrt{n \times m})$ walls there would be a significant speed up for large enough matrices. $\endgroup$
    – Phylliida
    Commented Apr 4, 2015 at 5:41
  • $\begingroup$ This can probably converted to bichromatic nearest neighbor computation in $L_1$ metric with polygonal(unit square) obstacles. $\endgroup$
    – Chao Xu
    Commented Apr 4, 2015 at 19:02
  • $\begingroup$ $O(n \log n)$ time would do($n$ is the number of walls and source vertices) From each goal node compute the shortest path distance to all the source nodes and use that to figure out the final value. link.springer.com/article/10.1007/BF01758836 $\endgroup$
    – Chao Xu
    Commented Apr 5, 2015 at 16:08
  • $\begingroup$ This does not necessarily answer your question, but here is a rather similar result which allows after preprocessing certain constant-time queries for shortest path on planar graphs: mimuw.edu.pl/~kowalik/papers/paths.pdf $\endgroup$
    – Joe Bebel
    Commented Apr 6, 2015 at 7:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.