List1包含大量 (~7^10) 的 N 维点 (N <=10)，List2包含相同或更少数量的 N 维点 (N <=10)。
我的任务是：对于 List1 中的每个点，我想检查 List2 中的哪个点最接近（欧几里德距离） List1 中的一个点，然后对其执行一些操作。我一直在做简单的嵌套循环方式，当我在 List1 中没有超过 50 个点时，但是有 7^10 个点，这显然会占用很多时间。
最快的方法是什么？计算几何中的任何概念可能会有所帮助？
编辑：我有以下内容，我已经从List2构建了一个 kd-tree ，然后现在我正在对List1中的每个点进行最近邻搜索。现在正如我最初指出的那样，List1有 7^10 个点，因此尽管我节省了每对的蛮力欧几里得距离方法，但List1中的大量点导致了大量的时间消耗。有什么办法可以改善吗？
一个好方法是使用 kd-tree 之类的东西并执行最近邻搜索。幸运的是，您不必自己实现此数据结构，之前已经完成。我推荐这个，但还有其他的：
如果不了解两种解决方案中点的分布，就不可能告诉您哪种算法最有效。然而，对于第一个猜测...
第一个算法不起作用- 有两个原因：（1）错误的假设 - 我假设边界外壳是不相交的，以及（2）对问题的误读 - 它没有找到每对点的最短边。
...计算两个集合的凸包：最近的点必须位于两个包的超面上，两个重心之间的线通过该超面上。
您可以通过计算中心点来计算凸包，假设所有点的质量相同，重心，然后将列表从离中心最远到最远排序。然后取出列表中最远的点，将其添加到凸包中，然后删除到目前为止计算的凸包内的所有点（您需要计算大量 10d 超三角形来执行此操作）。重复直到列表中没有任何东西不在凸包上。
第二种算法：部分
计算 List2 的凸包。对于 List1 的每个点，如果该点在凸包之外，则按照第一种算法找到超面：最近的点必须在该面上。如果是在脸上，同样如此。如果它在里面，你仍然可以通过将线延伸到 List1 的点来找到超面：最近的点必须在包含超面到 List2 重心的球内：但是，在这里，你需要一个新的算法来获得最近的点，也许是 kd-tree 方法。
性能
当 List2 通过一些相当倾斜的形状像均匀分布或正态分布时，这将很好地减少所考虑的点数，并且应该与 kd-tree 建议兼容。
但是，有一些可怕的麦芽汁情况：如果 List2 仅包含圆环表面上的点，其几何中心是列表的重心，那么凸包的计算将非常昂贵，并且对减少没有太大帮助考虑的点数。
我的评价
这些几何技术可能是对其他海报的 kd-trees 方法的有用补充，但在确定它们是否值得应用之前，您需要对点的分布有所了解。
kd-tree 非常快。我在本文中使用了该算法，它运行良好Bentley - 用于半动态点集的 Kd 树
我确信周围有图书馆，但很高兴知道有时会发生什么 - Bentley 很好地解释了这一点。
基本上，有多种搜索树的方法：最近的 N 个邻居、给定半径内的所有邻居、半径内的最近 N 个邻居。有时您想搜索有界对象。
这个想法是 kdTree 递归地划分空间。每个节点在您所在空间的一个维度中沿轴拆分为 2。理想情况下，它垂直于节点的最长维度拆分。您应该继续拆分空间，直到每个桶中有大约 4 个点。
然后对于每个查询点，当您递归访问节点时，检查您所在的特定节点到隔墙的距离。如果到隔墙的距离，则下降两个节点（您所在的节点及其兄弟节点）比搜索半径更近。如果墙超出半径，只需搜索您所在节点的子节点。
当您到达一个桶（叶节点）时，您测试那里的点以查看它们是否在半径内。
如果你想要最近的点，你可以从一个很大的半径开始，并在递归时传递一个指针或对它的引用——这样你就可以在找到接近点时缩小搜索半径——然后回到最近的点相当快。
（一年后）早早退出的 kd 树，在查看所有 200M 点中的 1M 之后，在高维度上可以快得多。
结果仅在统计上接近绝对最接近的值，具体取决于数据和指标；没有免费的午餐。
（请注意，采样 1M 点，而 kd 树仅采样 1M，是完全不同的，更糟。）
FLANN对 dim=128 的图像数据执行此操作，我相信 opencv。快速可靠的 SciPy cKDTree的本地模块也具有 cutoff= 。