Find the closest intersection point in the plan

Question

I was recently asked the following question:

Suppose you have a grid in a 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 procedure in which a list of locations of people (points) is given, find a location (point), one that is the closest point to the entire given point.

How would you solve this problem?

1) The approach is the kd tree, but do you know any other solution?

Answer 1

If the problem requires minimizing the Manhattan distance (i.e. people go only parallel to the axes), then the problem is then quite trivial. Firstly, choosing the x coordinate and y coordinate are independent issues.

Then, for each coordinate, simply find the median value of the position of people along this axis. For many configurations of people, there may be more than one point that minimizes the amount of running distances for all people. (Just think that 2 people are divided into more than 2 blocks along x and with the same y coordinate, and any intersection between them will require the same general walking of two people.)

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

Answer 2

Before starting to study the kd trees, these are some thoughts that came to my mind:

• Iterate over every point of your matrix, graph, or any other.
• Assign each point (x, y) a value representing MAX_distance from the Point to any of the people. (See example explanation below).
• Take any of the points with the smallest value MAX_distance

eg. This point (0,0):

• For (1,0) the distance is: 1
• For (2,0) the distance is: 2
• For (0.2) distance: 2
• For (3.1) distance: 4
• For (4.2), the distance is: 6

The value of MAX_distance for (0,0) is 6. Given your input, the minimum value of MAX_distance should be 3, and there are many points with a value like (2,1), for example.

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

Answer 3

This is likely to give you a more approximate than correct answer. But maybe you can try some kind of clustering (see Medical Image Processing)

What to do if you project all points on the Y axis:

  3* 4* 3* 

Then project onto the X axis:

 2* 2* 2* 2* 2* 

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

Now find the median using weight (weight @location = how many people are in this place along the axis)

If you find the median for both axes, you can take the meeting points as (median X, median).

You can get the correct nearest point if, when calculating the median on one axis, you must also minimize the distance by calculating the median of the other axis. This last case is more complicated.