2

我有 m 个地方(x,y 坐标)。

我有 n 个请求寻找到给定点 P(x,y) 的最近位置;(最小欧几里得距离)

我如何在 O(n*m) 以下解决这个问题,其中 n 是请求数,m 是位置数?我可以使用平方欧几里得距离,但它仍然是 n*m。

4

3 回答 3

1

试试kd-tree。可以在此处找到高性能库实现。

注意:我指的是针对高维度优化的近似最近邻搜索。这对您的应用程序来说可能有点矫枉过正。

编辑:

对于 2d kd-tree,构建时间为 O(m*log(m)),查询时间为 O(n*sqrt(m))。如果您的查询数 n 超过 log(m),这最终应该会胜过简单的解决方案。

该库意味着您不必实现它,因此复杂性不应该成为问题。

如果您想推广到高维极快查询,请查看localitysensitive hashing

于 2011-05-28T14:12:55.647 回答
0

最近邻问题,嗯?我发现Robert Sedgewick Std Book在这些情况下非常有用。他也描述了最近邻搜索

于 2011-05-28T14:31:40.483 回答
0

有趣的。为了减少 n 的影响,我想知道它是否有助于在您遇到并处理它时保存每个请求的结果。一个聪明的结果表可能会缩短在解决后续请求 时计算 sqrt( x 2 + y 2 ) 的需要。

于 2011-05-28T14:19:40.253 回答