最小的覆盖圈

Question

平面上有n个点,如何近似找到覆盖这些点中某些k的圆的最小半径？数字n应该小于10 ^ 4.

在维基百科中有关于案例k == n的大量信息,但我在一般情况下没有发现任何信息.

Answer 1

一种想法是，您可以以所有点的平均值为中心，然后增大半径，直到覆盖 k 个点。在相当均匀的分布下，这可能会做得很好，但对于“块状”数据会失败。例如，如果这些点位于两个彼此远离的紧密簇中，并且 k 小到只需要其中一个点，那么这将严重失败。如果存在这种聚集的可能性，请考虑使用聚类算法来识别局部聚类，然后如果其中一个聚类包含足够的点，则仅在该聚类上使用该算法。