找到计划中最近的交叉点

Question

我最近在采访中被问到以下问题：

假设你在笛卡尔坐标系（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) {

}

在给定人员位置（点）列表的情况下实施例程，找到最接近所有给定点的位置（点）。

你会如何解决这个问题？

1）方法是k-d树，但是你知道其他任何解决方案吗？

Answer 1

如果问题需要最小化Manhattan distance（也就是说，人们只能平行于轴行走），那么这个问题就非常微不足道了。首先，选择x坐标和y坐标是独立的问题。

然后，对于每个坐标，只需找到沿该轴的人的位置的中值。对于许多人的配置，可以有不止一个点最小化所有人的步行距离的总和。 （只考虑两个人在x和相同的y坐标中分开超过2个区块;两个人之间的任何交叉点都需要两个人相同的总步数。）

如果问题要求最小化欧几里德距离，那么目标是找到2变量L1中值。这是一个标准问题，但它远非微不足道。 （例如，请参阅here。）有一个独特的答案。鉴于这是一个面试问题，我怀疑这不适用。

Answer 2

在去研究k-d树之前，我想到了一些想法：

1. 迭代矩阵，图形或其他任何点
2. 为每个点（x，y）分配一个值，该值表示从Point到任何人的MAX_distance。 （见下面的澄清示例）
3. 取任何具有最低MAX_distance的点

例如。给定点（0,0）：

• 对于（1,0），距离为：1
• 对于（2,0），距离为：2
• 对于（0,2），距离为：2
• 对于（3,1），距离为：4
• 对于（4,2），距离为：6

（0,0）的MAX_distance为6.给定输入，最低MAX_distance应为3，并且有许多具有该值的点，例如（2,1）。

应该有办法使这个算法更有效。也许使用k-d树：p或其他调整，如检查总人数，他们的相对位置/距离，任何迭代的MAX_distance值等。

Answer 3

这可能会给你更多的近似而不是正确的答案。但也许你可以尝试某种聚类（参见医学图像处理）

如果将所有点投影到Y轴上，该怎么办：

 3*
 4*
 3*

然后投影到X轴：

2* 2* 2* 2* 2*

图例：3 *表示轴上此坐标处有3个人

现在也使用权重找到中位数（权重@location =轴上该位置的人数）

如果您找到两个轴的中位数，那么您可以将会合点作为（medianX，medianY）。

如果在一个轴上计算中位数时，可以得到正确的最近点，还可以通过计算另一个轴的中位数来确保最小化距离。后一种情况更难。