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

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

基本观察:

• 我假设半径是1,因为它不会改变任何东西。
• 给定任意两点,它们所在的单位圆最多有两个。
• 给定问题的解圆,可以移动它,直到它包含集合中的两个点,同时保持集合中相同数量的点。

算法如下:

• 计算C1和C2中集合的点数

这就是文献中的“磁盘部分覆盖问题”——这应该给你一个开始谷歌搜索的好地方。这是一篇关于一种可能的解决方案的论文,但在数学上有点紧张: Approximation Algorithms Design for Disk Partial Covering Problem

事实上,这属于计算几何学领域,这一领域很吸引人,但很难站稳脚跟。deBerg很好地概述了与该主题相关的各种算法。

如果你想做一些简单的事情,随机选择一个位置(x,y),计算圆内的点数,并与之前的位置进行比较。取最大值。随时重复该操作。

这里有两个想法:O(n)近似算法和O(n^2 logn)精确(非近似)算法:

快速逼近

使用位置敏感哈希。基本上,将每个点散列到包含所有附近点的散列桶中。桶的设置使得冲突只发生在附近的点之间——与类似命名的哈希表不同,这里的冲突很有用。记下一个桶里的碰撞次数,然后用这个桶的中心作为你的圆心。

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

更多关于 locality-sensitive hashes in general 或关于 my personal favorite version that would work in this case .

优于暴力确定性方法

其思想是:对于每个点,将一个圆的边放在该点上,然后扫一圈,看看哪个方向包含的点最多。对所有点这样做,我们就找到了全局最大值。

点p周围的扫描可以在n logn时间内完成,方法是:(a)求出每个点q的角度间隔,这样当我们把圆放在θ角时,它就包含q;(b)对时间间隔进行排序,以便我们可以在线性时间内围绕p进行行进/扫描。

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

问题又回到找到 全球的 :R x R -> N . 的输入 f

f ,然后加强围绕这些点的搜索(例如沿着螺旋向外移动)。

另一个选择是考虑 连接集合中任意点对的线段交点。你的 我想在这些交叉点之一,但它们的数量可能太大,无法考虑。

您还可以混合选项1和2,并考虑由“良好设定点”周围的点生成的线段的交点。

认为 你可以保证找到最佳的(只是一个好的解决方案)。

此外,还有一种称为K-means的信息可视化/数据挖掘方法,它可以对给定的数据进行聚类。它可以与附加功能一起使用,以满足您的目的。

K-均值的基本算法是:

1. 这些点表示初始组质心
2. 将每个数据项分配给最接近的组 质心
3. 通过计算点的平均位置来确定K个质心的位置
4. 重复步骤2和3,直到质心不再移动或移动很少

5. 计算位于K个质心的圆内的点数

资料来源:
Linköping University
四叉树- en.wikipedia.org/wiki/Quadtree

在wikipedia上快速搜索,您可以找到源代码: en.wikipedia.org/wiki/K-means_clustering

如果精度确实不重要,而且算法可能会犯一些小错误,那么我认为如下几点。

让 f(x,y) f(x,y) = e^{(x^2 + y^2)/ (2 * R^2)} .

让 (x_i,y_i) 是点和 E_i(x,y) = f(x - x_i, y - y_i)

你的问题是找到 \sum_i E_i(x,y)

你可以从每个点开始使用梯度下降。

我可以推荐一张密度图吗?求x和y的最小和最大界限。将x和y边界的范围划分为宽度等于圆直径的容器。分别计算每个箱子中x和y的点数。现在在你的密度图上找到最高等级的x垃圾箱和最高等级的y垃圾箱之间的交叉点。

这是一个非常快速的算法,可以快速概括大型数据集,但并不总是准确的,为了提高准确性,您可以将存储箱分割成越来越小的部分,或将存储箱位置向左或向右移动n次,并使用投票系统来选择在两次试验之间最常出现的答案。

当然,由于舍入错误,您可能会丢失一些好的区域或“幻觉”好的区域。也许你可以先做一个粗略的像素化,然后再细化有前景的区域。

这就是著名的K-最近点算法。描述如下: http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf