我有非空的 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)
更新
距离是指欧氏距离
最佳答案
使用 kd-tree 可以获得 O(log N) 时间.这就像一棵二叉搜索树，只是它首先在 x 维度上拆分点，然后在 y 维度上拆分点，然后再在 x 维度上拆分点，依此类推。
如果您的点是均匀分布的，您可以通过将点分箱到大小均匀的框中然后搜索查询点所在的框及其八个框来实现 O(1) 查找相邻的盒子。
很难从 Voronoi 图得出有效的解决方案，因为这需要您解决确定查询点落入哪个 Voronoi 单元的问题。大部分时间这涉及构建 R* 树来查询Voronoi 单元的边界框(O(log N) 时间)，然后执行多边形中的点检查(O(p)多边形的周长)。
关于algorithm - 优化搜索最近点的暴力解决方案，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49443866/