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|)$.

  • $\begingroup$ Quoting the answer to the linked question, "In grassfire the distances are constant." $\endgroup$ Sep 17 '19 at 14:15
  • $\begingroup$ @Yuval Filmus The distances in BFS are constant as well. $\endgroup$
    – J. Schmidt
    Sep 17 '19 at 14:42
  • $\begingroup$ "Grassfire is actually based on a small modification of BFS." $\endgroup$ Sep 17 '19 at 14:50
  • $\begingroup$ @Yuval Filmus I can read $\endgroup$
    – J. Schmidt
    Sep 17 '19 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$ Sep 17 '19 at 14:53

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.


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.