I cant tell from the abstract TBH. I'd have to do some digging (when I get back from holidays). I'm sure I've cited it in my own scientific work at the time. - Almar On Thu, Jul 16, 2020, at 17:09, Brenda Prallon wrote:

Hi Almar,

Thank you so much for your quick response. Do you remember by any chance if the paper was the following one? https://doi.org/10.1002/net.3230070404

Once again, thank you!

Em qua., 15 de jul. de 2020 às 17:57, Almar Klein <almar.klein@gmail.com> escreveu:

...

__ Hi Brenda,

This is all from the top of my head because I dont have access to a computer right now. I recall that at its base the algorithm was based on a paper, which in essence described the application of Dijkstras algirithm on a regular grid (i.e. an image).

So at its core its not new. It is implemented in a way that allows it to be used in a flexible way.

The speed and memory efficiency can probably be attributed to (the implementation of) the binary heap.

Regards,

Almar

On Wed, Jul 15, 2020, at 15:57, Brenda Prallon wrote:

...

Hi everyone,

I was hoping to get some theoretical details on the algorithm of find_costs for the MCP and MCP_Geometric classes. I am not a computer scientist, so I've had some trouble drawing conclusions from the source code alone; I hope someone can help me :)

First, let me give you some context (although the questions don't depend on it): I am trying to find the most efficient way possible to solve the following problem: I have a (4359, 4950) raster and 5000 georeferenced points. I need to find the shortest path between all these points (basically, the output would be the triangle part of a symmetric matrix). I have run some tests using MCP, MCP_Geometric and the package "gdistance" in R, which claims to implement Djikistra's algorithm in the costDistance function (it actually relies on package "igraph", which use C written functions in the background as well). MCP.find_costs() and MC_Geometric.find_costs() have performed consistently better, even for a small sample of points (e.g. 10), so I am skeptical that the difference is due to R being slower than Python (plus, I've run the examples on a jupyter notebook). Not only that, but while MCP and MCP_Geometric don't use more than 1GB of RAM memory, the examples in R use more than 10GB.

So, firstly, what I would like to ask is:

1- What is the algorithm implemented in MCP? Is it simply Djikstra's, some other known algorithm, or something new? 2- If it is something new, what would be the complexity? 3- How is it so memory efficient?

At last I wanted to check if I got something straight: the difference of MCP.find_costs() to MCP_Geometric.find_costs() is just that in MCP_Geometric the matrix of costs needs to be recalculated before running the algorithm, is that right? Or does it affect the internal process of finding the shortest path in some other way?

Thank you for reading this far :) This implementation seems very unique and efficient, and I am just trying to better understand it. -- Brenda _______________________________________________ scikit-image mailing list -- scikit-image@python.org To unsubscribe send an email to scikit-image-leave@python.org https://mail.python.org/mailman3/lists/scikit-image.python.org/ Member address: almar.klein@gmail.com

-- Brenda