• Advertisement
Sign in to follow this  

Finding minimum distance of points along a 2D grid

This topic is 2260 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Here's an interesting question for everyone.

Say you have a 2D grid with length X and width Y. You have N points in this grid (existing in some cell of the grid). It is possible for more than one point to be in the same grid position. Moving a point to a neighboring spot in the grid (horizontal and vertical, no diagonal movement) takes 1 unit. Find the spot on the grid that allows you to move all points to one grid cell with the least amount of travel cost.

+ - + - P - + - +
| | | | |
P - + - + - + - +
| | | | |
+ - P - + - + - +

(the 5 |'s are suppose to be spaced out but I guess the editor doesn't like that)

+'s are grid cells, - are horizontal movements | are vertical movements, P is a point in a grid cell. The answer for this example is position (2, 2) requiring 4 moves, 2 from the top middle point, 1 each of the other two points.

My brute force solution to this was to check the required distance traveled for each node in the grid. The one (or more than one) with the minimum traveled distance is the solution. This requires O(XY) comparisons.

I know there is a better solution to this and I believe that this problem is very similar to finding the center of many points, just forced to fit along a grid. I thought of taking the average of all points but that doesn't work for a lot of cases.

Anyone have suggestions on how to solve this with a better time complexity than the brute force method?

Share this post


Link to post
Share on other sites
Advertisement
I think what you want to look for is the center of the sample points. That is find the center in the given random sample points such that the distance between all points to that center is minimal. Google center star algorithm. I think this problem is in NP and thus you might have to settle for an approximation algorithm. Note, I maybe wrong about my method but the above is my initial thought.

Share this post


Link to post
Share on other sites
Use a code block if you want it to look right:+ - + - P - + - +
| | | | |
P - + - + - + - +
| | | | |
+ - P - + - + - +

Your brute force algorithm is actually O(NXY) because for each cell it has to calculate the distance required to get there from each of the N points.
That's not terribly bad, but if the grid is 5000 * 5000 and there are 2000 points then it could be slow.

I have an idea that is O(NX + NY) ...
Basically you calculate the cost for the horizontal and vertical movements of all points separately, then find the minimum sum of the combinations of horizontal moves plus vertical moves.

E.g. for the above board you calculate the cost of moving all points to each column
Column => Cost
1 => 3
2 => 2
3 => 3
4 => 6
5 => 9

Row => Cost
1 => 3
2 => 2
3 => 3

Now you iterate over the rows and columns and pick the minimum sum from each.
2 is smallest from the columns and 2 is smallest from the rows = total of 4, at position (2, 2)
All this does is avoid repeatedly calculating the same horizontal costs for each vertical position and vice versa.

It might be possible to do better, but I'd probably just do this.

Share this post


Link to post
Share on other sites
Couldn't you do a flood fill of distances from each point? The pseudocode for my suggestion (you need to keep track of the distances from each point to each location):
  1. Fill in the locations with a distance 1 higher then the distance you last looked at (so if you looked at locations 1 distant from each point you would look at locations 2 distant from each points) from each point
  2. Examine all the points that you filled in step 1 to see if any of them have distances to all points, and rank them on the sum of the distances
  3. Either you stop because you know that you have the smallest such sum (admittedly I do not know how to do this at the moment) or go back to step 1



Share this post


Link to post
Share on other sites
This problem can be solved in linear time to the number of the input points.

As iMalc pointed, the problem is separable to two applications of 1D scans through the input points, to first solve for X, and then for Y. This is the case since you don't allow diagonal movements. Taxicab distance makes things simpler!

To solve the problem in 1D:

- You are given an array of input points N_1, N_2, ..., N_k, integers, and you need to find an integer K such that

a) Max | N_i - K | is minimized, or

b) Sum | N_i - K | is minimized.

I am unsure which one you were after, so for both:

In the case A, take the average of the minimum and maximum value, round to integer.

In the case B, first sort the points into ascending order (can be done in linear time with radix or bucket sort), then perform a linear pass through the array. At each iteration, you can compute the "penalty" caused by leaving the past points behind, and the gain received by moving the center point forward. At some point, these two balance, and you know you have the optimal center point. (In fact, I'm thinking it could perhaps be converted into log-time binary search, but I'd have to implement it to see if that's the case).

Share this post


Link to post
Share on other sites
Actually, I think the problem is as simple as computing the median of the X coordinates and the median of the Y coordinates. Indeed, this can be solved in linear time.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement