select 点与最周围点的最有效方法
Most efficient way to select point with the most surrounding points
N.B：问题底部有一个重大修改 - 检查一下
问题
假设我有一组点：
我想在该点的半径 
（即一个圆）或 
（即一个正方形）范围内的 2 维范围内找到其周围点数最多的点。我将其称为最密集点函数。
对于这个问题中的图表，我会将周围区域表示为圆圈。在上图中，中间点的周围区域显示为绿色。这个中间点在半径 内的所有点中具有最周围的点，将由最密集点函数返回。
我试过的
解决这个问题的可行方法是使用范围搜索解决方案； 进一步解释，它有“
worst-case 时间”。使用这个，我可以获得每个点周围的点数，并选择周围点数最多的点。
但是，如果这些点非常密集（大约一百万），例如：
那么这百万个点 (
) 中的每一个都需要执行范围搜索。 worst-case时间，其中
是范围内返回的点数，适用于以下点树类型：
二维的- kd-trees（其实稍微差一点，在
），
- 二维范围树，
- 四叉树，其 worst-case 时间为
因此，对于组内所有点的半径 内的一组 
个点，每个点的复杂度为 
。这会产生超过一万亿次操作！
关于实现此目的的更有效、更精确的方法的任何想法，以便我可以在合理的时间（最好是 
或更短的时间内找到一组点中最周围点的点)?
编辑
原来上面的方法是正确的！我只需要帮助实现它。
(半)解
如果我使用二维范围树：
- 范围报告查询成本
，对于 
个返回点，
- 对于具有部分级联的范围树（也称为分层范围树），复杂度为
、
- 对于2维，即，
- 此外，如果我执行范围计数查询（即，我不报告每个点），则成本为
。
我会在每一点上执行此操作 - 产生我想要的 复杂度！
问题
但是，我不知道如何编写二维分层范围树的计数查询代码。
我找到了关于范围树的 great resource (from page 113 onwards)，包括二维范围树伪代码。但是我不知道如何引入分数级联，也不知道如何正确实现计数查询，使其具有 O(log n) 复杂性。
我还发现了两个范围树实现 here and here in Java, and one in C++ here，尽管我不确定这是否使用了分数级联，因为它在 countInRange 方法上方指出
It returns the number of such points in worst case
* O(log(n)^d) time. It can also return the points that are in the rectangle in worst case
* O(log(n)^d + k) time where k is the number of points that lie in the rectangle.
这对我来说表明它不应用分数级联。
细化问题
因此，为了回答上面的问题，我需要知道的是是否有任何具有带分数级联的 2d 范围树的库具有复杂度 的范围计数查询，所以我不去重新发明任何轮子，或者你能帮我 write/modify 上面的资源来执行那种复杂的查询吗？
如果你能给我提供任何其他方法以任何其他方式实现中二维点的范围计数查询，也不抱怨！
我会先创建类似 https://en.wikipedia.org/wiki/K-d_tree 的东西，其中有一棵树，叶子上有点，每个节点都有关于其后代的信息。在每个节点，我都会记录后代的数量，以及包含这些后代的边界框。
现在对于每个点我都会递归搜索树。在我访问的每个节点，要么所有的边界框都在当前点的 R 内，要么所有的边界框都离当前点 R 远，要么一部分在 R 内，一部分在 R 外。在第一个案例我可以使用当前节点的后代数来增加当前点的 R 内的点数，并 return 向上递归一级。在第二种情况下，我可以简单地 return 向上一层递归而不增加任何东西。只有在中间情况下，我才需要继续向下递归树。
所以我可以计算出每个点在 R 中的邻居数，而无需检查每个其他点，然后选择计数最高的点。
如果这些点均匀分布，那么我认为你最终会构建一个 k-d 树，其中较低的层次接近于一个规则的网格，我认为如果网格的大小是 A x A，那么在最坏的情况下情况 R 足够大，因此它的边界是一个与 O(A) 低级单元相交的圆，所以我认为如果你有 O(n) 个点，你可以预期它的成本约为 O(n * sqrt(n)) .
您可以通过在 O(n) 时间内预处理数据来估计相邻点的数量来加快您使用的任何算法。
对于半径为 R 的圆，创建一个网格，其单元格在 x 和 y 方向上的尺寸都为 R。对于每个点，确定它属于哪个单元格。对于给定的单元格 c 此测试很简单：
c.x<=p.x && p.x<=c.x+R && c.y<=p.y && p.y<=c.y+R
（你可能要深入思考一下闭区间还是半开区间是否正确。）
如果你有相对dense/homogeneous的覆盖率，那么你可以使用数组来存储值。如果覆盖率是 sparse/heterogeneous，您可能希望使用哈希图。
现在，考虑网格上的一个点。单元格内点的极值位置如下所示：
单元格角点的点只能与四个单元格中的点相邻。沿边的点可以与六个单元格中的点相邻。不在边上的点与 7-9 个像元中的点相邻。由于一个点很少会恰好落在角落或边缘上，我们假设焦点单元中的任何点都与所有 8 个周围单元中的点相邻。
因此，如果点 p 在单元格 (x,y) 中，N[p] 标识了p 在半径 R 内的邻居，Np[y][x] 表示单元格 (x,y) 中的点数，那么 N[p] 由以下公式给出：
N[p] = Np[y][x]+
Np[y][x-1]+
Np[y-1][x-1]+
Np[y-1][x]+
Np[y-1][x+1]+
Np[y][x+1]+
Np[y+1][x+1]+
Np[y+1][x]+
Np[y+1][x-1]
一旦我们为每个点估计了邻居的数量，我们就可以在 O(n) 时间内将该数据结构堆到最大堆中（例如 make_heap）。该结构现在是一个优先级队列，我们可以在 O(log n) 时间内根据估计的邻居数量对每个查询进行排序。
对第一个点执行此操作并使用 O(log n + k) 圆搜索（或一些更聪明的算法）来确定该点的实际邻居数.在变量 best_found 中记下这一点并更新其 N[p] 值。
查看堆的顶部。如果估计的邻居数量少于 N[best_found] 那么我们就完成了。否则，重复上述操作。
要改进估计，您可以使用更精细的网格，如下所示：
连同一些巧妙的滑动 window 技术来减少所需的处理量（例如，参见 this answer 对于矩形情况 - 对于圆形 windows 你应该使用FIFO 队列的集合）。为了提高安全性，您可以随机化网格的原点。
再次考虑您提出的示例：
很明显，这种启发式方法有可能节省大量时间：使用上述网格，只需执行一次昂贵的检查即可证明中间点具有最多的邻居。同样，更高分辨率的网格将改进估计并减少需要进行的昂贵检查的数量。
您可以而且应该将类似的边界技术与 mcdowella's answers 结合使用；然而，他的回答并没有提供一个好的开始寻找的地方，所以可能会花很多时间探索低价值点。
我建议使用 plane sweep algorithm。这允许一维范围查询而不是二维查询。 （哪个更高效，更简单，并且在方形邻域的情况下不需要分数级联）：
- 按 Y 坐标将点排序到数组 S。
- 提前3个指向数组S的指针：一个（C）为当前检查的（中心）点；另一个，A（稍微提前一点）距离> R低于C的最近点；最后一个，B（稍微落后一点）代表距离 < R 以上的最远点。
- 将A指向的点插入Order statistic tree（按坐标X排序）并从这棵树中删除B指向的点。使用这棵树找到距 C 到 left/right 距离为 R 的点，并使用这些点在树中位置的差异来获取 C 周围方形区域中的点数。
- 使用上一步的结果 select "most surrounded" 点。
如果您旋转点（或仅交换 X-Y 坐标）以使占用区域的宽度不大于其高度，则可以优化此算法。您也可以将点切割成垂直切片（具有 R 大小的重叠）并分别处理切片 - 如果树中的元素太多以至于它不适合 CPU 缓存（这不太可能只有 100 万点）。该算法（优化与否）的时间复杂度为 O(n log n).
对于圆形邻域（如果 R 不太大且点分布均匀），您可以用几个矩形近似圆形：
在这种情况下，算法的第 2 步应该使用更多指针以允许 insertion/removal to/from 多棵树。在第 3 步中，您应该在适当距离 (<=R) 的点附近进行线性搜索，以区分圆内的点和圆外的点。
另一种处理圆形邻域的方法是用等高的矩形近似圆形（但这里的圆形应该被分割成更多的部分）。这导致算法更简单（其中使用排序数组而不是顺序统计树）：
- 将点占据的区域切割成水平切片，切片按Y排序，然后切片内的点按X排序。
- 对于每个切片中的每个点，假设它是一个 "center" 点并执行步骤 3。
- 对于每个附近的切片，使用二分搜索找到欧氏距离接近 R 的点，然后使用线性搜索从 "outside" 中区分出 "inside" 个点。在切片完全在圆内的地方停止线性搜索，并根据数组中的位置差计算剩余点。
- 使用上一步的结果 select "most surrounded" 点。
此算法允许前面提到的优化以及分数级联。
N.B：问题底部有一个重大修改 - 检查一下
问题
假设我有一组点：
我想在该点的半径 （即一个圆）或
（即一个正方形）范围内的 2 维范围内找到其周围点数最多的点。我将其称为最密集点函数。
对于这个问题中的图表，我会将周围区域表示为圆圈。在上图中，中间点的周围区域显示为绿色。这个中间点在半径 内的所有点中具有最周围的点，将由最密集点函数返回。
我试过的
解决这个问题的可行方法是使用范围搜索解决方案； worst-case 时间”。使用这个，我可以获得每个点周围的点数，并选择周围点数最多的点。
但是，如果这些点非常密集（大约一百万），例如：
那么这百万个点 () 中的每一个都需要执行范围搜索。 worst-case时间
，其中
是范围内返回的点数，适用于以下点树类型：
-
二维的
- kd-trees（其实稍微差一点，在
- 二维范围树，
- 四叉树，其 worst-case 时间为
因此，对于组内所有点的半径 内的一组
个点，每个点的复杂度为
。这会产生超过一万亿次操作！
关于实现此目的的更有效、更精确的方法的任何想法，以便我可以在合理的时间（最好是 或更短的时间内找到一组点中最周围点的点)?
编辑
原来上面的方法是正确的！我只需要帮助实现它。
(半)解
如果我使用二维范围树：
- 范围报告查询成本
- 对于具有部分级联的范围树（也称为分层范围树），复杂度为
- 对于2维，即
- 此外，如果我执行范围计数查询（即，我不报告每个点），则成本为
我会在每一点上执行此操作 - 产生我想要的 复杂度！
问题
但是，我不知道如何编写二维分层范围树的计数查询代码。
我找到了关于范围树的 great resource (from page 113 onwards)，包括二维范围树伪代码。但是我不知道如何引入分数级联，也不知道如何正确实现计数查询，使其具有 O(log n) 复杂性。
我还发现了两个范围树实现 here and here in Java, and one in C++ here，尽管我不确定这是否使用了分数级联，因为它在 countInRange 方法上方指出
It returns the number of such points in worst case * O(log(n)^d) time. It can also return the points that are in the rectangle in worst case * O(log(n)^d + k) time where k is the number of points that lie in the rectangle.
这对我来说表明它不应用分数级联。
细化问题
因此，为了回答上面的问题，我需要知道的是是否有任何具有带分数级联的 2d 范围树的库具有复杂度 的范围计数查询，所以我不去重新发明任何轮子，或者你能帮我 write/modify 上面的资源来执行那种复杂的查询吗？
如果你能给我提供任何其他方法以任何其他方式实现中二维点的范围计数查询，也不抱怨！
我会先创建类似 https://en.wikipedia.org/wiki/K-d_tree 的东西，其中有一棵树，叶子上有点，每个节点都有关于其后代的信息。在每个节点，我都会记录后代的数量，以及包含这些后代的边界框。
现在对于每个点我都会递归搜索树。在我访问的每个节点，要么所有的边界框都在当前点的 R 内，要么所有的边界框都离当前点 R 远，要么一部分在 R 内，一部分在 R 外。在第一个案例我可以使用当前节点的后代数来增加当前点的 R 内的点数，并 return 向上递归一级。在第二种情况下，我可以简单地 return 向上一层递归而不增加任何东西。只有在中间情况下，我才需要继续向下递归树。
所以我可以计算出每个点在 R 中的邻居数，而无需检查每个其他点，然后选择计数最高的点。
如果这些点均匀分布，那么我认为你最终会构建一个 k-d 树，其中较低的层次接近于一个规则的网格，我认为如果网格的大小是 A x A，那么在最坏的情况下情况 R 足够大，因此它的边界是一个与 O(A) 低级单元相交的圆，所以我认为如果你有 O(n) 个点，你可以预期它的成本约为 O(n * sqrt(n)) .
您可以通过在 O(n) 时间内预处理数据来估计相邻点的数量来加快您使用的任何算法。
对于半径为 R 的圆，创建一个网格，其单元格在 x 和 y 方向上的尺寸都为 R。对于每个点，确定它属于哪个单元格。对于给定的单元格 c 此测试很简单：
c.x<=p.x && p.x<=c.x+R && c.y<=p.y && p.y<=c.y+R
（你可能要深入思考一下闭区间还是半开区间是否正确。）
如果你有相对dense/homogeneous的覆盖率，那么你可以使用数组来存储值。如果覆盖率是 sparse/heterogeneous，您可能希望使用哈希图。
现在，考虑网格上的一个点。单元格内点的极值位置如下所示：
单元格角点的点只能与四个单元格中的点相邻。沿边的点可以与六个单元格中的点相邻。不在边上的点与 7-9 个像元中的点相邻。由于一个点很少会恰好落在角落或边缘上，我们假设焦点单元中的任何点都与所有 8 个周围单元中的点相邻。
因此，如果点 p 在单元格 (x,y) 中，N[p] 标识了p 在半径 R 内的邻居，Np[y][x] 表示单元格 (x,y) 中的点数，那么 N[p] 由以下公式给出：
N[p] = Np[y][x]+
Np[y][x-1]+
Np[y-1][x-1]+
Np[y-1][x]+
Np[y-1][x+1]+
Np[y][x+1]+
Np[y+1][x+1]+
Np[y+1][x]+
Np[y+1][x-1]
一旦我们为每个点估计了邻居的数量，我们就可以在 O(n) 时间内将该数据结构堆到最大堆中（例如 make_heap）。该结构现在是一个优先级队列，我们可以在 O(log n) 时间内根据估计的邻居数量对每个查询进行排序。
对第一个点执行此操作并使用 O(log n + k) 圆搜索（或一些更聪明的算法）来确定该点的实际邻居数.在变量 best_found 中记下这一点并更新其 N[p] 值。
查看堆的顶部。如果估计的邻居数量少于 N[best_found] 那么我们就完成了。否则，重复上述操作。
要改进估计，您可以使用更精细的网格，如下所示：
连同一些巧妙的滑动 window 技术来减少所需的处理量（例如，参见 this answer 对于矩形情况 - 对于圆形 windows 你应该使用FIFO 队列的集合）。为了提高安全性，您可以随机化网格的原点。
再次考虑您提出的示例：
很明显，这种启发式方法有可能节省大量时间：使用上述网格，只需执行一次昂贵的检查即可证明中间点具有最多的邻居。同样，更高分辨率的网格将改进估计并减少需要进行的昂贵检查的数量。
您可以而且应该将类似的边界技术与 mcdowella's answers 结合使用；然而，他的回答并没有提供一个好的开始寻找的地方，所以可能会花很多时间探索低价值点。
我建议使用 plane sweep algorithm。这允许一维范围查询而不是二维查询。 （哪个更高效，更简单，并且在方形邻域的情况下不需要分数级联）：
- 按 Y 坐标将点排序到数组 S。
- 提前3个指向数组S的指针：一个（C）为当前检查的（中心）点；另一个，A（稍微提前一点）距离> R低于C的最近点；最后一个，B（稍微落后一点）代表距离 < R 以上的最远点。
- 将A指向的点插入Order statistic tree（按坐标X排序）并从这棵树中删除B指向的点。使用这棵树找到距 C 到 left/right 距离为 R 的点，并使用这些点在树中位置的差异来获取 C 周围方形区域中的点数。
- 使用上一步的结果 select "most surrounded" 点。
如果您旋转点（或仅交换 X-Y 坐标）以使占用区域的宽度不大于其高度，则可以优化此算法。您也可以将点切割成垂直切片（具有 R 大小的重叠）并分别处理切片 - 如果树中的元素太多以至于它不适合 CPU 缓存（这不太可能只有 100 万点）。该算法（优化与否）的时间复杂度为 O(n log n).
对于圆形邻域（如果 R 不太大且点分布均匀），您可以用几个矩形近似圆形：
在这种情况下，算法的第 2 步应该使用更多指针以允许 insertion/removal to/from 多棵树。在第 3 步中，您应该在适当距离 (<=R) 的点附近进行线性搜索，以区分圆内的点和圆外的点。
另一种处理圆形邻域的方法是用等高的矩形近似圆形（但这里的圆形应该被分割成更多的部分）。这导致算法更简单（其中使用排序数组而不是顺序统计树）：
- 将点占据的区域切割成水平切片，切片按Y排序，然后切片内的点按X排序。
- 对于每个切片中的每个点，假设它是一个 "center" 点并执行步骤 3。
- 对于每个附近的切片，使用二分搜索找到欧氏距离接近 R 的点，然后使用线性搜索从 "outside" 中区分出 "inside" 个点。在切片完全在圆内的地方停止线性搜索，并根据数组中的位置差计算剩余点。
- 使用上一步的结果 select "most surrounded" 点。
此算法允许前面提到的优化以及分数级联。