我需要回答很多关于在远离查询点的点集中寻找最近邻居的问题。到目前为止我发现的所有方法在这种情况下都不好用(例如，k-d 树每个查询可能有 O(N))或需要使用 Voronoi 图(我有 ~10m 点所以 Voronoi 图太贵了)。
是否有为此类任务设计的已知算法？
最佳答案
这里的问题是距离。你看，当查询距离你的数据集很远时，kd-tree 必须检查很多点，从而减慢查询时间。
您面临的情况通常对于最近邻结构来说很难(而且这不是通常的情况)，但如果我是您，我会尝试使用 Balanced Box-Decomposition trees ，您可以在其中阅读有关其算法和数据结构的更多信息。
关于algorithm - 远离点集的查询点的 3D 最近邻，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39925801/