Algorithm: Remote conversion - any faster algorithm?

Question

I am trying to solve a distance conversion problem (using Manhattan distance). In principle, giving a matrix with 0 and 1, the program should assign the distances of each position to the nearest 1. For example, for this

0000 0100 0000 0000 

distance conversion matrix

 2123 1012 2123 3234 

Possible solutions from my head:

The slowest ones (slower because I tried to implement them), they lagged behind on very large matrices):

• Brute-force - for every 1 that the program reads, it changes distances from the beginning to the end, respectively.

• Width search from scratch - for every 0 the program searches for the nearest 1 inside out.

• Same as 2, but starting from 1 mark at each distance inside out.

• Much faster (read other people's code)

  First search from level 1

   1. Assign all values in the distance matrix to -1 or very big value. 2. While reading matrix, put all positions of 1 into queue. 3. While queue is not empty a. Dequeue position - let it be x b. For each position around x (that has distance 1 from it) if position is valid (does not exceed matrix dimensions) then if distance is not initialized or is greater than (distance of x) + 1 then I. distance = (distance of x) + 1 II. enqueue position into queue 

I wanted to ask if there is a faster solution to this problem. I tried to find algorithms for converting distance, but most of them deal with Euclidean distances.

Thanks in advance.

Answer 1

In the first search for the width, operations Θ(n*m) performed, where n and m are the width and height of your matrix.

You need to print the numbers Θ(n*m) , so you cannot get faster than from a theoretical point of view.

I assume that you are not interested in discussing discussions using the cache and such optimizations.

---

Please note that this solution works in more interesting cases. For example, imagine the same question, but there may be different “sources”:

 00000 01000 00000 00000 00010 

Using BFS, you will get the following path to the closest source with the same complexity:

 21234 10123 21223 32212 32101 

However, with one source, there is another solution that may have slightly higher performance in practice (although the complexity remains the same).

Before that, let's observe the following property.

Property : if the source is in (a, b), then the point (x, y) has the following Manhattan distance:

 d(x, y) = abs(x - a) + abs(y - b) 

This should be fairly easy to prove. So another algorithm:

 for r in rows for c in cols d(r, c) = abc(r - a) + abs(c - b) 

which is very short and light.

---

If you do not write and test it, there is no easy way to compare the two algorithms. Assuming an efficient implementation of a limited queue (with an array), you have the following basic operations for a cell:

• BFS: insert / delete a queue, visit each node 5 times (four times in neighbors and once from a queue)
• Direct formula: two subtractions and two if s

It will really depend on the compiler and its optimizations, as well as on the specific processor architecture and memory, to say which will work better.

Nevertheless, I would advise you to go with what seems simpler to you. However, note that when using multiple sources in the second solution, you will need several passes in the array (or several distance calculations in one pass), and this will certainly have worse performance than BFS for a sufficiently large number of sources.

Answer 2

You do not need a queue or anything like that. Note that if (i, j) is at a distance d from (k, l), one way to understand is that the distance should go left or right | ik | times and then up or down | jl | time.

So, initialize your matrix with large numbers and insert zero wherever you have 1 . Now do something like this:

 for (i = 0; i < sx-1; i++) { for (j = 0; j < sy-1; j++) { dist[i+1][j] = min(dist[i+1][j], dist[i][j]+1); dist[i][j+1] = min(dist[i][j+1], dist[i][j]+1); } dist[i][sy-1] = min(dist[i][sy-1], dist[i][sy-2]+1); } for (j = 0; j < sy-1; j++) { dist[sx-1][j] = min(dist[sx-1][j], dist[sx-2][j]+1); } 

At this point, you have found all the shortest paths that are associated only with the move or on the right. If you do a similar thing to move up and left, dist[i][j] will give you the distance from (i, j) to the closest 1 in your input matrix.