0
$\begingroup$

Expanding on this question :

Why is Dijkstra's Algorithm more popular compared to Grassfire algorithm?

What are the differences between grassfire and BFS? I'm surprised grassfire (supposedly) has a complexity of only $O(|V|)$, whereas BFS has a complexity of $O(|V| + |E|)$.

$\endgroup$
  • $\begingroup$ Quoting the answer to the linked question, "In grassfire the distances are constant." $\endgroup$ – Yuval Filmus Sep 17 at 14:15
  • $\begingroup$ @Yuval Filmus The distances in BFS are constant as well. $\endgroup$ – J. Schmidt Sep 17 at 14:42
  • $\begingroup$ "Grassfire is actually based on a small modification of BFS." $\endgroup$ – Yuval Filmus Sep 17 at 14:50
  • $\begingroup$ @Yuval Filmus I can read $\endgroup$ – J. Schmidt Sep 17 at 14:51
  • $\begingroup$ Grassfire runs in time $O(|V|)$ since a 2D grid has $|E| = \Theta(|V|)$. Grassfire (as described on Wikipedia) has only two passes, whereas BFS can have many iterations. $\endgroup$ – Yuval Filmus Sep 17 at 14:53
1
$\begingroup$

Grassfire seems to be simply a BFS in a 2D grid graph. Since $|E| = \Theta(|V|)$ in a 2D grid graph, this results in a complexity of $O(|V| + |E|) = O(|V|)$.

See also Wikipedia's page on the similar grassfire transform (https://en.wikipedia.org/wiki/Grassfire_transform), a computation of the distance from some pixel(s) to the border of a region in an image, which can be used to yield descriptors such as the region's skeleton or medial axis.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.