最近邻3D，带删除和添加操作

Question

是否存在支持删除和添加操作以及精确的最近邻查询的最近邻数据结构？寻找一个理想的Python实现。在

尝试次数：

• 在高维空间中发现了许多近似近邻查询的实现。在
• 找到了KD树和球树，但它们不允许动态再平衡。在
• 认为一个算法可以用局部敏感散列实现。在
• 看八叉树。在

上下文：

1. 对于10000个点的每个点，查询其最近的邻居
2. 评估每对邻居
3. 选择一个并删除这对点并添加一个合并点。在
4. 重复一些迭代

Answer 1

是的。存在这样一个数据结构。我发明了一个。我手头正是这个问题。这种数据结构使得KD树显得过于复杂。它只由点所具有的每个维度中的点的排序列表组成。在

显然，您可以从按其各自维度排序的n个列表中添加和删除n维点，这非常简单，没有问题。很多技巧可以让你迭代这些列表，并从数学上证明你有最短的距离到一个点。请参阅我的答案here，了解详细说明和代码。在

我必须指出，你的背景是错误的。A的最近点可能是B，但它并不认为B的最近点一定是A。你可以装配一个点链，使每个链接之间的距离小于之前的距离，但也必然比其他点更远，从而导致只有1对邻居共享其最近邻居。在