c++ - C++中2点之间的最小距离

Question

我有 m 个位置(x，y 坐标)。

我有 n 个请求找到离给定点 P(x,y) 最近的地方； (最小欧氏距离)

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

Answer 1

试试kd-tree .可以找到高性能库实现 here .

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

编辑:

对于 2d kd-tree，构建时间为 O(m*log(m))，查询时间为 O(n*sqrt(m))。如果您的查询数量 n 超过 log(m)，这最终应该是对天真的解决方案的净赢。

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

如果您想推广到高维极速查询，请查看 locality sensitive hashing .