Find the Closest intersection point in plan

问题:

I was asked following question in interview recently:

Let suppose you have, following grid on Cartesian coordinate system ( Quadrant I).

o - x - x - x - o
|   |   |   |   |
x - x - x - o - x
|   |   |   |   |
x - o - o - x - x

where,  o => person at intersection  and  x => no person at intersection

class Point {
 int x;
 int y;
 boolean hasPerson;
}


Point findNearestPointWhereAllPeopleCanMeet(Point[] people) {

}

Implement a routine where given a list of people location (points), find a location(point) such that is closest point to all given point.

How would you solve this problem ?

1) Approach is k-d tree, but do you know any other solution ?

回答1:

If the problem calls for minimizing the Manhattan distance (that is, people only walk parallel to the axes), then the problem is then pretty trivial. First, selecting the x coordinate and the y coordinate are independent problems.

Then, for the each coordinate, simply find the median value of the position of the people along that axis. For many configurations of people, there can be more than one point that minimizes the sum of the walking distances of all people. (Just consider 2 people separated by more than 2 blocks in x and at the same y coordinate; any intersection in between will require the same total walking by the two people.)

If the problem calls for minimizing the Euclidean distance, then the goal is to find the 2-variable L1 median. This is a standard problem, but it is far from trivial. (See here, for instance.) There is a unique answer. Given that this was an interview question, I suspect that this does not apply.

回答2:

Before going to study k-d trees these are some thoughts that came to my mind:

1. Iterate every point of your matrix, graph, or whatever it is
2. Assign to each point (x,y) a value representing the MAX_distance from the Point to any of the people. (See a clarification example below)
3. Take any of the points that have the lowest MAX_distance

E.G. Given Point(0,0):

• For (1,0) the distance is: 1
• For (2,0) the distance is: 2
• For (0,2) the distance is: 2
• For (3,1) the distance is: 4
• For (4,2) the distance is: 6

The MAX_distance for (0,0) is 6. Given your input the lowest MAX_distance should be 3 and there are many Points with that value like (2,1) for instance.

There should be ways to make this algorithm more efficient.. Maybe with k-d trees :p or with other tweaks like checking the total number of people, their relative location/distance, the MAX_distance value at any iteration, etc..

回答3:

This will probably give you more of an approximate than the correct answer. But maybe you can try some sort of clustering (see medical image processing)

What if you project all points onto the Y axis:

 3*
 4*
 3*

Then project onto the X axis:

2* 2* 2* 2* 2*

Legend: 3* means 3 people at this coordinate on the axis

Now find the median also using the weights (weight @location = how many people at that location on axis)

If you find the median for both axis then you could take the meeting points as (medianX, medianY).

You could get the correct closest point if when you calculate median on one axis, you also make sure to minimize distance by calculating the median of the other axis. This latter case is harder.