<p>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.</p>

<p>The propogation rule is simple: For each node, check if any of its <a href="http://en.wikipedia.org/wiki/Von_Neumann_neighborhood" rel="nofollow">4 neighbors</a>' 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.</p>

<p><strong>Given $O(1)$ nodes, is it possible to compute their final propagation values in asymtotically less than $O(nm)$ time?</strong></p>

<p>Edit:</p>

<p>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&lt;n, y&lt;m\}$:</p>

<ol>
<li>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)$.</li>
<li>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)</li>
<li>Repeat 2 until the grid is full and no more propagation can occur.</li>
</ol>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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&lt;n, y&lt;m\}$ that don't allow their value to be modified in step 2.</p>

<p><em>With walls, is it possible to compute the value of any $O(1)$ goal nodes in asymptotically less than $O(nm)$ time?</em></p>

CC BY-SA 3.0
2014-06-28T19:28:16.910Z
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?
usul
CC BY-SA 3.0
2015-04-04T05:41:05.657Z
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.
Phylliida
CC BY-SA 3.0
2015-04-04T19:02:42.947Z
This can probably converted to bichromatic nearest neighbor computation in $L_1$ metric with polygonal(unit square) obstacles.
Chao Xu
CC BY-SA 3.0
2015-04-05T16:08:04.027Z
$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. http://link.springer.com/article/10.1007/BF01758836
Chao Xu
CC BY-SA 3.0
2015-04-06T07:01:23.463Z
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: http://www.mimuw.edu.pl/~kowalik/papers/paths.pdf
Joe Bebel
<graph-algorithms><ai.artificial-intel><shortest-path>
Efficiently computing propagation values for only a few positions in a grid
Phylliida
# Efficiently computing propagation values for only a few positions in a grid

(Asked by: username_0 on 2014-06-28)

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](http://en.wikipedia.org/wiki/Von_Neumann_neighborhood)' 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

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

*With walls, is it possible to compute the value of any $O(1)$ goal nodes in asymptotically less than $O(nm)$ time?*

**Tags:** graph-algorithms, ai.artificial-intel, shortest-path

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.  
> **username_2**: This can probably converted to bichromatic nearest neighbor computation in $L_1$ metric with polygonal(unit square) obstacles.  
> **username_2**: $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. http://link.springer.com/article/10.1007/BF01758836  
> **username_3**: 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: http://www.mimuw.edu.pl/~kowalik/papers/paths.pdf  

---

## 0 answers

