algorithm - 给定一组 2D 点和最大距离，找到中心点为集合点的最小簇

Question

给定一组二维点(相当小)和最大距离，找到最小簇数，其中对于每个簇，内部所有点之间的距离为最大距离的半径。集群的中心应该是那些点之一。此外，给出每个簇内的点数。

好像是k-means之类的东西，不过是给了最大距离。我没有看到比测试所有可能性更好的解决方案(最大簇数是点数)。有更好的解决方案吗？

Answer 1

正如 Anony-Mousse 所说，您的问题似乎与 set cover problem “相关” .使用与维基百科页面中相同的符号和术语，宇宙 U 是您的点集，而集合 S 包含 |U| 集，为 U 中的每个点 u 设置一个这样的集合，包含圆盘内以 u 为中心的所有点，半径等于您的最大值距离。所以你的问题是在 S 中找到最小数量的集合(相当于找到应该是簇中心的点)使得这些集合的并集是 U.

现在，我上面所做的是将您的问题简化为布景封面问题。这是我们想要执行归约的错误方向，以表明您的问题可能是“困难的”。要做到这一点，需要证明布景问题的每个实例都可以改写为您的问题的一个实例。

但是，您说您的点数很少。您可以像上面那样定义集合 S 然后对其进行暴力破解(即尝试所有可能的 S 子集合并获取其中集合数量最少的集合，导致 |S| 的大小呈指数复杂度)。对于这种方法，您实际上希望 S 中的集合数量相当少，点数并不那么重要。