优化搜索最近点的暴力解决方案

Question

我有非空的 Set 散布在平面上的点，它们由坐标给出。问题是快速回复此类查询：

Give me the point from your set which is nearest to the point A(x, y)

我目前的解决方案伪代码

query( given_point )
{
  nearest_point = any point from Set
  for each point in Set
    if dist(point, query_point) < dist(nearest_point, given_point)
      nearest_point = point
  return nearest_point
}

但是这个算法很慢，复杂度是O(N)。

问题是，是否有任何数据结构或带有预计算的棘手算法可以显着降低时间复杂度？我至少需要 O(log N)

更新

我说的距离是欧氏距离

Answer 1

如果不进行预处理，您肯定需要花费 O(N)，因为您必须查看 return 最近的每个点。

您可以在此处 Nearest neighbor search 查看如何解决此问题。

Answer 2

您可以使用 kd-tree 获得 O(log N) 时间。这就像一个二叉搜索树，只是它首先在 x-dimension 上拆分点，然后在 y-dimension 上拆分点，然后再次在 x-dimension 上拆分点，依此类推。

如果你的点是均匀分布的，你可以实现 O(1) look-up 通过将点分箱到 evenly-sized 个盒子然后搜索盒子查询点落在其中及其八个相邻框。

很难从 Voronoi 图做出有效的解决方案，因为这需要您解决确定查询点落入哪个 Voronoi 单元的问题。大部分时间这涉及构建 R* 树以查询 Voronoi 单元的边界框（在 O(log N) 时间内）然后执行 point-in-polygon 检查 (O(p) 多边形周长中的点数）。

Answer 3

您可以将网格划分为多个小节：

根据点数和网格大小，选择有用的划分。让我们假设一个 1000x1000 像素的屏幕，充满随机点，均匀分布在表面上。

你可以将屏幕分成10x10的部分，然后做一个地图(roughX, roughY)->(List((x, y), ...)。对于某个点，你可以查找图中的所有点相同的单元格并且 - 由于该点可能更接近相邻单元格的点而不是同一单元格中的极值点，因此周围的单元格甚至可能相距 2 个单元格。这会将搜索范围缩小到 16 个单元格。

如果在同一层中找不到点cell/layer，请将搜索扩展到下一层。

如果您碰巧在下一层中找到下一个邻居，则必须将搜索范围扩大到每一层的附加层。如果点太多，选择更细的网格。如果点数太少，则选择更大的网格。请注意，用一条线连接到红色的两个绿色圆圈与红色圆圈的距离相同，但一个在第 0 层（同一单元格），另一个在第 2 层（下一个单元格的下一个）。

优化搜索最近点的暴力解决方案

Optimize bruteforce solution of searching nearest point

algorithm

computational-geometry