algorithm - 如何找到特定大小的点簇

Question

给定一个点列表，我想找到 N 个点的所有“集群”。我对集群的定义很松散，可以调整为任何允许最简单的解决方案：它可以是某个大小圆圈内的 N 个点，也可以是彼此相距一定距离内的 N 个点或其他有意义的点。启发式是可以接受的。

其中 N = 2，我们只是在寻找所有靠近在一起的点对，使用 kd 树很容易高效地完成（例如，递归地将空间分成八分圆或其他东西，其中每个区域都是不同的分支树，然后对于每个点，将其与具有相同父级的其他点进行比较（如果靠近区域的边缘，请检查适当的级别数）。我认识到，通过 N=N' 的解决方案进行归纳，我可以通过取不同 N' 解决方案之间的交集来找到 N=N'+1 的解决方案，但这是非常低效的。

任何人都知道一个体面的方法来解决这个问题？

Answer 1

您首先计算欧几里得最小生成树，例如CGAL可以做到这一点。从那里开始，精确的算法取决于您的具体要求，但大致如下：您按长度对该图中的边进行排序。然后删除边，从最长的开始。这是一个单连接图，因此对于每个删除的边，您都可以将图分成两个子图。检查每个创建的子图是否根据您的条件形成集群。如果没有，继续删除边。