问半径为r以覆盖n个点的最小圆数

EN

这可能不是最好的解决方案，但请尝试优化它。

算法基于随机抽样：

1. 在地图上生成N个圆
2. 删除未覆盖任何点的所有圆
3. 按覆盖点数降序排序
4. (已排序)-将圆覆盖的点标记为已覆盖。如果圆没有覆盖任何新点，请从列表中删除。

这是你可以现场预览的代码：http://jsfiddle.net/rpr8qq4t/示例结果(每30个点13个圆)：

​

参数化：

  var POINTS_NUMBER = 30;
  var RADIUS = 50;
  var SAMPLE_COUNT = 400;

可能会添加一些优化(例如，某些圆圈可能过早地从列表中排除)

编辑

步骤1中的

1. 更改带来了更好的结果:为每个点生成N个圆(圆至少覆盖一个点)新版本：http://jsfiddle.net/nwvao72r/3/

编辑2(最终算法)

最后：

1. 每一个点生成一个离点的随机距离小于R(圆的半径)的N=10圆，因此我们可以确定对于每个圆，至少有一个点属于它，并且每个点属于至少一个点，直到所有的点都被覆盖：
   • get圆覆盖了最大数量的未覆盖的点。将点标记为covered.

​

这是为我带来最好结果的版本，你可以在这里检查它， http://jsfiddle.net/nwvao72r/4/平均每30个点有12个圆圈。

​

​

我确信这个问题是NP难的，尽管我不打算在这里尝试和证明这一点。

如果它是NP难的，那么为了找到一个保证最优的解决方案，我推荐以下方法：

1. 查找所有“良好”的潜在圆位置，以及每个记录中包含哪些点。
2. 使用这些点集解决集合覆盖问题。(这个问题是NP难的。)

好的圆圈位置

给定任何两个相距小于2r的点，正好有两个半径为r的圆穿过这些点：

​

​

编辑:我最初对“最好的”圆圈的描述是错误的，尽管这不会导致问题--感谢评论者george描述了正确的思考方式。

如果一个圆覆盖了一个最大的点集(这意味着该圆不能被重新定位以覆盖相同的点集加上至少1个以上的点)，那么这个圆可以四处滑动，直到它的边界恰好接触到它覆盖的两个点--比如说，向左滑动直到它接触到一个已经覆盖的点，然后顺时针旋转它，直到它接触到另一个已经覆盖的点。这个移动的圆将精确地覆盖原始圆覆盖的一组点。此外，我们永远不需要考虑覆盖非极大点集的圆，因为覆盖这些点和更多点的最大圆至少同样有用，并且不需要更多成本。这意味着我们只需要考虑接触两点的圆。如果我们为输入中的每一对足够接近的点生成两个圆，我们就已经生成了我们可能需要的所有圆。

因此，我们的潜在圆池每对点最多包含2个圆，总共最多有n*(n-1)个潜在圆。(通常会有较少的点，因为一些点对的距离通常会超过2r，因此无法由半径为r的单个圆覆盖。)此外，对于距离任何其他点超过2r的每个点，我们都需要一个额外的圆--这些圆也可以以这些远程点为中心。

设置封面

我们真正关心的是每个势圆所覆盖的点的集合。因此，对于每个可能的圆，找到它所覆盖的点。这可以在O(n^3)时间内完成，对每个潜在的圆使用O(n)遍。为了稍微加快速度，如果我们发现两个不同的圆覆盖了完全相同的点集，我们只需要保留其中一个圆(覆盖的点集)。此外，我们还可以丢弃任何作为其他覆盖点集的子集的覆盖点集--在这种情况下，选择较大的覆盖点集总是更可取的。

最后，我们有一个覆盖点集的集合，我们希望找到这些集合中覆盖每个点的最小子集。这是set cover problem。我不知道解决此问题的特定算法，但branch and bound是解决此类问题的标准方法--它通常比更简单的穷举回溯搜索快得多。我会首先通过找到一个(或多个)启发式解决方案来启动搜索，希望能产生一个很好的上限，从而减少分支和边界搜索时间。我认为即使是最好的算法在最坏的情况下也需要指数级的时间，尽管我认为对于n< 20这是可以处理的，因为最多有19*18 = 342个不同的点集。

摘自Gautam K.Das et的论文"On the Disk Disk Cover Problem“。al.：

最小几何磁盘盖板。在最小几何圆盘覆盖问题中，输入由平面上的一组点组成，问题是找到一组具有最小基数的单位圆盘，其并集覆盖这些点。与DUDC不同，磁盘中心不被约束为从给定的离散集中选择，而是可以在平面中的任意点上居中。同样，这个问题是NP-hard 9，并且有一个PTAS解决方案11，12。

参考文献：

1. R.Fowler，M.Paterson和S.TAnimoto，飞机中的最佳包装和覆盖是NP-complete，信息处理快报，第12卷，第133-137页，1981。
2. G. Frederickson，平面图中最短路径的快速算法及其应用，SIAM J. on Computing，第16卷，第1004-1022页，1987年。
3. T. Gonzalez，覆盖多维空间中的一组点，信息处理快报，40卷，第181-188页，1991。
4. D.Hochbaum和W. Maass，用于图像处理和超大规模集成电路中覆盖和包装问题的近似方案，J.ACM，第32卷，第130-136页，1985。