Minimum number of moves required for converging between 3 points in m*n matrix

Question

I have a (m*n) matrix, in which lies 3 different points. I have to find the minimum number of moves such that all 3 points converge at a point inside the matrix.

Solution(s) I have tried till now:

• Brute force solution: Try all the points in the matrix, find the point which needed the minimum moves from the 3 given points.
• Bound the three points as a triangle and try the points with in this region. This will more likely to be the centroid of this triangle.

I would like to know about other optimized solutions for this problem. Thanks.

Answer 1

For Manhattan distance:

Simply take the middle x-coordinate and the middle y-coordinate of the 3 points as the target. By middle I mean the median of the sorted coordinates.

Example:

Input: (1,5), (2,4), (3,6)

The x-points are 1, 2 and 3 (sort to 1, 2, 3). The middle one is 2.

The y-points are 5, 4 and 6 (sort to 4, 5, 6). The middle one is 5.

Thus the point that minimizes the distance is (2,5).

Proof:

If we were to start at the above mentioned point and move in any direction, the distance to the point we're moving towards would decrease and the distance to the other 2 points would increase, thus every move by 1 would cause a total decrease of 1 but a total increase of 2. Once we've moved past the last point, all 3 distances would increase, thus the total increase will be 3 with no decrease. Thus any move causes an increase in distance, thus the above point is optimal.

For Euclidean distance:

(I realize now that you said minimum moves, thus this is probably not what you want)

This is somewhat more complicated. It involves minimizing this equation:

sqrt((x-x1)^2 + (y-y1)^2) + sqrt((x-x2)^2 + (y-y2)^2) + sqrt((x-x3)^2 + (y-y3)^2)

Because of the sqrt's, one cannot simplify the equation by saying that x and y are distinct.

However, the greedy approach is likely to work:

• Pick any point (maybe the one that minimizes the Manhattan distance is a good start).
• While one of the neighbouring points of the picked point results in lower euclidean distance, pick that point.

Answer 2

Each move you change either x- or y- coordinates by +/- 1. Vertical and horizontal distances are that way independent. So, firstly lead points to one x-coordinate, then y-coordinate. The most optimal way of doing it is moving points with minimal and maximal x to the x-position of the third point. Repeat same for y and you are done.

This way the coordinate of that final point is x coordinate of middle point on x-axis and y coordinate of middle point on y-axis (there can be many such points though, but this must be one of the minimizing set). (if they overlap, obviously either of the overlapping coordinates will be middle one).

Programmatically take an array of x-values, remove max and min values, same with y and you'll be left with your closest-to-all point.

Answer 3

I think this is one of the variants of the http://en.wikipedia.org/wiki/Steiner_tree_problem - probably the http://en.wikipedia.org/wiki/Rectilinear_Steiner_tree problem. This looks sufficiently intimidating that I would stick to trying all points within the triangle.

Actually with just points converging on a single point I think sashkello is right