algorithm - 删除点以最大化最短最近邻距离

Question

如果我在 2D 空间中有一组N个点，由它们位置的向量 X 和 Y 定义。什么是有效的算法

1. 选择一个固定数量（M）个点进行移除，以最大化剩余点之间的最短最近邻距离。
2. 删除最少数量的点，以使剩余点之间的最短最近邻距离大于固定距离（D）。

按最短最近邻距离对点进行排序并删除具有最小值的点并不能给出正确的答案，因为然后您删除了靠近对的两个点，而您可能只需要删除这些对中的一个点。

就我而言，我通常处理 1,000-10,000 点，我可能会删除 50-90% 的点。

Answer 1

除了蛮力方法，我想不出任何办法。但是您可能会在进行任何分析之前显着缩短您正在查看的数据集。

所以，我会做的是。首先计算出每个点的最近邻距离。让我们称之为P_in。然后计算出每个点到其M最近邻居的最大距离，称之为P_iM。如果P_in大于P_iM任何点，则可以将其从分析中排除。基本上，如果您有一个点与任何其他点的距离为 10，并且您还有另一个点与最近的点的距离为 9，M那么您应该删除第一个点。

根据集群的级别或有多大M，这可能会大大减少您的数据集。

Answer 2

诺姆

一种方法是将 2D 空间分成 N 个分区。在每个分区内，确定每个 X、Y 的平均位置。然后对平均点执行最近邻算法。然后对匹配的分区的完整点集重复最近邻测试。

这就是问题所在。分区越大，获得的点数越少，但准确度越低。分区越小，它会更准确，但需要处理的点更多。

Answer 3

您不需要存储（或计算）整个距离矩阵：Delaunay 三角剖分应该有效地（O(n log n)最坏的情况）为您提供点集的最近邻居。您还应该能够在删除点时有效地更新它。

对于大多数靠近对的情况，您应该能够检查如果另一个被删除，哪一个离它的邻居最远。这不是一个精确的解决方案；特别是如果您删除大部分点，则删除局部最优点可能会排除全局最优解。此外，您应该能够处理由 3 个或更多本地接近点组成的集群。但是，如果您只是从随机分布的集合中删除一小部分点，那么这两种情况可能都比较少见。

可能有也可能没有更好的方法（即精确和有效的算法）来解决您的问题，但上述建议应该导致一种近似和/或组合方法，当需要删除的点分布稀疏时效果最佳。