从给定的n个点中选择最接近的k个点

Question

从给定的n个点中选择最接近的k个点

algorithmlanguage-agnosticgeometrycomputational-geometry

22

给定一个平面上的点集 U，其中有 n 个点，您可以在常数时间内计算任意两点之间的距离。选出 U 的一个子集 C，使得 C 恰好包含 k 个点，并且 C 中最远的两点之间的距离对于给定的 k 最小。1 < k ≤ n

除了明显的 n-choose-k 解决方案，有什么更快的方法吗？

- pathikrit

我有一种感觉这个问题是NP完全问题，如果有一个已知的NP完全问题的简化草图也可以。 :) - pathikrit

完成-已接受答案（尽管只是一个期刊论文的链接） - pathikrit

6个回答

9

由于这是一个面试问题，以下是我的解决方案。（正如下面的dcn指出的那样，虽然它不能保证返回最优解，但仍应该是一种不错的启发式方法。dnc发现得好！）

步骤： 1.创建具有单个点P的集合Sp。 2.计算Sp中每个点与其外部的每个点之间的距离，然后将具有最小最大距离的点添加到Sp中。 3.重复步骤2，直到Sp具有k个点。 4.使用每个点一次作为初始P来重复步骤1-3。选择具有最小最大距离的Sp。

Sp中有O（k）个点，Sp之外有O（n）个点，因此找到具有最小最大距离的点是O(nk)。我们重复k次，然后整个过程再次重复n次，总复杂度为O(n^2 * k^2)。

我们可以通过缓存Sp中任何点与Sp之外每个点之间的最大距离来改进。如果maxDistanceFromPointInS[pointOutsideS]是一个O(1)哈希表，其中包含点pointOutsideS和Sb子集内某个点之间当前的最大距离，则每次添加新点newPoint时，我们为所有Sp之外的点p设置maxDistanceFromPointInS[p]=Max(maxDistanceFromPointInS[p], distance(newPoint, p))。然后，找到最小的最大距离是O(n)，向Sp添加点是O(n)。重复k次给出O（（n + n）k）= O（nk）。最后，我们将整个过程再次重复n次，总体复杂度为O(n^2 * k)。

我们可以使用堆将查找最小最大距离改进到O（1），但这不会改变总体复杂度。

顺便说一下，编写这篇文章花了一个小时-我绝对不能在面试中做到这一点。

- BlueRaja - Danny Pflughoeft

谢谢您提供这个指针 - 这不是我问过的面试问题，但我在考虑是否应该问一下，至少可以看看他们的思维方式。 - pathikrit

3

你会如何回答这个问题？我认为问一个自己无法回答的问题是不公平的。 - BlueRaja - Danny Pflughoeft

你所描述的解决方案采用了一些启发式方法，但并不能提供最优解。另外，我认为你给出的参考文献有误，因为它是关于一个不同的问题的：“最小k覆盖圆”和“最远点之间的距离...[最小化]”并不相同（考虑等边三角形的情况！） - dcn

1

为什么最小的k-包围圆不同：考虑一个边长为a的等边三角形。包含所有3个端点的最小圆的半径为r=3a/sqrt(a)>a/2。现在取另外三个点，使它们共线且距离为r-epsilon。它们适合于半径为r-epsilon的圆中（该圆比三角形的圆更小），然而两组三个点中的最大距离是2*(r-epsilon) vs a（对于三角形情况）。 - dcn

1

为什么你的解决方案不起作用：取一个边长为a的等边三角形。现在在平面上添加三个点：每个三角形的角落都有一个，远离三角形，距离三角形角落为b=a-epsilon（类似于星形）。对于每个初始P，你的算法在第二步的第一次迭代中总是会选择长度为b的边缘。然而，k=3的正确解决方案是中间的三角形！ - dcn

显示剩余3条评论

1

这仍然是一个混乱的想法，~~我不确定它是否真正可行~~它不起作用。将错误答案留在这里，供后人参考。

For each point in U
    make a list of the distance to each point in U
    sort the list
    add largest distance to a max-heap.
while any of the lists have more than k elements
    remove max of heap twice
    remove corresponding elements from the two lists they came from
    add the two newly exposed largest elements from those two lists to the heap
Any of the lists left with k elements will list the elements in C

基本上，找到两个点，它们目前看起来都可以在子集中一起，而且它们之间的距离最大，然后排除它们同时在子集中的可能性。重复此过程，直到只剩下一种形成k大小子集的可能方式。

这应该具有时间复杂度O（（n ^ 2）log（n））和空间复杂度O（n ^ 2）。

- Null Set

贪心算法不适用，因为你可能会选择C={x,y1,y2}，其中x-y1和x-y2的距离很小，但y1和y2彼此之间相距很远。 - pathikrit

0

显然可以在确定性多项式时间内完成。

但我不理解他们的算法。似乎他们选择的圆总是输入点之一。有人能够解释一下或者简洁地解释一下他们在做什么吗（只需要第二部分）？

- pathikrit

看我的评论，里面有@BlueRaja - Danny Pflughoeft的答案。这篇论文是关于另一个问题的！ - dcn

那么，“找到至少包含k个点的n个给定点中最小的圆（半径和中心）”和“从给定的n个点中找到k个点的子集，使得所选子集中任意两点之间的最大距离最小化”的问题是不同的问题吗？ - pathikrit

1

是的，正如我的反例所示。然而，我在你上面链接的论文中找到了“你”的问题。请看看我的答案。 - dcn

0

实际提出的问题似乎很难。如果点不在平面上并且具有任意距离，则通过从k-clique进行归约（取任意未加权图，并为缺失的边添加长度无限的边和长度为1的现有边--当“最接近的k个点”具有最大相互距离为1而不是无穷大时存在大小为k的团），它将是NP-hard问题。然而，由于点被限制在平面上，因此禁止这种距离标记，可能会有解决方案。至少，它似乎可以接受近似解决。

如果您的面试意味着“包含k个点的最小直径圆”，那么以下可能是您在面试中可以合理想到的最快正确算法：

对于每组大小为3的集合，计算包含这些点的最小圆，并检查每个点是否包含在此圆中。如果包含的数量至少为k，则相应地更新最小直径。

基本上，这是一个四重嵌套的for循环，因此运行时间为O(n^4)。

- jonderry

这将提供一个很好的近似，但并不完全正确。例如，当k=3时，假设你有三个点，它们之间相距1个单位（直径=1.154...）。在其他地方，有2个点相距1.1个单位，并且有第三个点位于它们之间（直径=1.1）。你的算法会错误地选择后者三个点。 - Tom Sirgedas

根据我的理解，1.1是这个问题实例的正确返回值，因此这不是反例。*编辑：哦，好的，我明白你的意思了。 - jonderry

-2

如果您没有太多异常值，这应该是一个很好的近似解决方案。

p = mean center (average x, y) of U
M = U sorted by distance to p
C = M[0:k]

- limscoder

近似解决方案永远不够好。这个肯定会失败。 - Snowbear

4

@Snowbear: 我真不想成为那个需要教你NP完全问题的人... - BlueRaja - Danny Pflughoeft

近似解决方案是棘手的陷阱，因为您必须证明它们的误差界限和运行时间。当然，在现实生活中，您可以进行其他优化，例如查找集群等。 - pathikrit

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dcn · Accepted Answer

一种解决方案在《查找最小直径中的k个点及相关问题》 - Aggarwal, 1991 中展示。

所述算法的运行时间为: O(k^2.5 n log k + n log n)

对于那些无法访问论文的人：

称为 k-直径 的问题定义为: 查找一组具有最小直径的k个点。集合的直径是集合中任意两个点之间的最大距离。

我无法真正地概述所提出的算法，但它包括计算点的 (3k-3)阶Voronoi图，然后在每个 O(kn) Voronoi 集中解决问题（通过计算一些二分图中的最大独立集）...我想我是在说它非常不平凡，远远超出了面试和此网站的范围 :-)