c++ 中两点之间的最小距离
我有 m 个位置（x，y 坐标）。
我有 n 个请求，要求找到距离给定点 P(x,y) 最近的位置； （最小欧几里德距离）
我怎样才能在 O(n*m) 以下解决这个问题，其中 n 是请求数，m 是位置数？我可以使用欧几里得距离平方，但它仍然是 n*m。
I'm given m places (x,y coordinates).
I have n requests of finding the closest place to a given point P(x,y); (The minimum Euclidian distance)
How can i solve this problem below O(n*m) where n is the number of requests and m the number of places? I could use squared Euclidian distances but it's still n*m.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
尝试kd-tree。可以在此处找到高性能库实现。
注意：我向您指出针对高维度进行优化的近似最近邻搜索。这对于您的应用程序来说可能有点过分了。
编辑：
对于 2d kd-tree，构建时间为 O(m*log(m))，查询时间为 O(n*sqrt(m))。如果您的查询数量 n 超过 log(m)，那么这最终应该是对简单解决方案的净胜利。
该库意味着您不必实现它，因此复杂性不应该成为问题。
如果您想推广到高维极快查询，请查看局部敏感哈希。
Try a kd-tree. A high performance library implementation can be found here.
Note: I'm pointing you to an approximate nearest-neighbors search which is optimized for high dimensions. This may be slightly overkill for your application.
Edit:
For a 2d kd-tree, the build time would be O(m*log(m)) and the query time would be O(n*sqrt(m)). This should end up being a net win over the naive solution if your number of queries n, exceeds log(m).
The library means you don't have to implement it so the complexity shouldn't be an issue.
If you want to generalize to high dimension extremely fast querying, check out locality sensitive hashing.
有趣的。为了减少 n 的影响，我想知道在您遇到并处理每个请求时保存它的结果是否会有所帮助。聪明的结果表可能会在解决后续请求时缩短计算 sqrt( x2 + y2) 的需要。
Interesting. To reduce the effect of n, I wonder if perhaps it would help to save the result of each request as you encounter and handle it. A clever result table might shortcut the need to calculate sqrt( x2 + y2) in solving subsequent requests.
最近邻问题，是吗？我发现 Robert Sedgewick Std Book 在这些情况下非常有用。他还描述了最近邻搜索。
The Nearest-Neighbor-Problem, eh? I found Robert Sedgewick Std Book very useful in these cases. He describes Nearest Neighbour Search, too.