用给定半径的一个圆覆盖最大点数的算法

Question

让我们想象一下,我们有一架飞机上有一些点.我们还有一个给定半径的圆.

我需要一种算法来确定圆圈的位置,它可以覆盖最大可能的点数.当然,有很多这样的位置,所以算法应该返回其中一个.
精度并不重要,算法可能会犯很小的错误.

这是一个示例图片:

输入:
  int n(n <= 50) - 点数;
  float x[n]和float y[n]- 具有点X和Y坐标的数组;
  float r - 圆的半径.

输出:
  float cx和float cy- 圆的中心坐标

算法的闪电速度不是必需的,但它不应该太慢(因为我知道这种情况的一些慢速解决方案).

C++代码是首选,但不是强制性的.

Answer 1

编辑为更好的措辞,如建议:

基本观察:

• 我假设半径是一,因为它不会改变任何东西.
• 给定任意两点,它们至多存在两个单位圆.
• 给出问题的解决方案循环,你可以移动它直到它包含你的集合中的两个点,同时保持你的集合中的相同点数.

然后算法是:

• 对于每对点,如果它们的距离<2,则计算通过它们的两个单位圆C1和C2.
• 计算C1和C2内的集合点数
• 拿最大值

Answer 2

这是文献中的"磁盘部分覆盖问题" - 应该为您提供一个开始使用Google搜索的好地方.这是一篇涵盖一种可能的解决方案的论文,但它在数学上有点激烈:http: //www.utdallas.edu/~edsha/papers/bin/ISPAN04_cover.pdf

事实上,这属于称为计算几何的领域,这很有吸引力,但很难获得立足点.德伯格对与该主题相关的各种算法有一个很好的概述.

Answer 3

如果你想要简单的东西,采取随机位置(x,y),计算圆内的点数并与之前的位置进行比较.取最大值.您可以随时重复操作.

为什么地狱投票？有没有听过蒙特卡罗的方法？实际上对于大量的点,确定性算法可能无法在合理的时间内完成.

Answer 4

这里有两个想法：O(n) 近似算法和 O(n^2 log n) 精确（非近似）算法：

快速逼近

使用局部敏感哈希。基本上，将每个点散列到包含所有附近点的散列桶。存储桶的设置使得冲突仅发生在附近的点之间 - 与名称类似的哈希表不同，冲突在这里很有用。记录桶中的碰撞次数，然后使用该桶的中心作为圆的中心。

我承认，这是对一个概念的快速解释，当您第一次听到它时，它并不是非常明显。打个比方，询问一群人的邮政编码是什么，然后使用最常见的邮政编码来确定人口最多的圈子。它并不完美，但却是一个很好的快速启发式方法。

就点数而言，它基本上是线性时间，并且您可以动态更新数据集，以在每个点的恒定时间内逐步获得新答案（相对于 n = 点数为常数）。

有关一般位置敏感哈希的更多信息或有关我个人最喜欢的在这种情况下适用的版本的信息。

优于暴力的确定性方法

这个想法是：对于每个点，将圆的边缘放在该点上，然后扫动圆以查看哪个方向包含最多的点。对所有点执行此操作，我们找到全局最大值。

围绕点 p 的扫描可以在 n log n 时间内完成，方法是： (a) 找到每个其他点 q 的角度间隔，这样当我们以角度 theta 放置圆时，它包含 q；(b) 对间隔进行排序，以便我们可以在线性时间内围绕 p 行进/扫掠。

因此，需要 O(n log n) 时间来找到接触固定点 p 的最佳圆，然后将其乘以 O(n) 以对所有点执行检查。总时间为 O(n^2 log n)。