Find the Closest intersection point in plan

Question

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 ?

Answer 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.

Answer 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..