给定一个 k 维连续（欧几里得）空间，其中充满了相当不可预测的移动/增长/收缩超球体，我需要反复找到其表面最接近给定坐标的超球体。如果某些超球体与我的坐标的距离相同，则最大的超球体获胜。（保证超球体的总数随着时间的推移保持不变。）
我的第一个想法是使用KDTree，但它不会考虑超球体的非均匀体积。所以我进一步观察，发现BVH（Bounding Volume Hierarchies）和BIH（Bounding Interval Hierarchies）似乎可以解决问题。至少在 2-/3 维空间中。然而，虽然在 BVHs 上找到了相当多的信息和可视化，但我在 BIHs 上几乎找不到任何东西。
我的基本要求是考虑体积的k 维空间数据结构，并且构建速度超快（离线）或动态几乎没有任何不平衡。
鉴于我上面的要求，你会使用哪种数据结构？还有什么我没有提到的吗？
编辑1：忘了提：hypershperes 被允许（实际上是高度期望的）重叠！
编辑2：看起来我描述的度量标准不是“距离”（特别是“负距离”）更匹配一个点的力量。
我希望 QuadTree/Octree/泛化为 2^K-tree，因为您的 K 维数可以解决问题；这些递归地划分空间，并且假设您可以在 K-subcube（或 K-矩形砖，如果分裂不均匀）不包含超球体，或包含一个或多个超球体以致分区不分离任何超球体时停止，或者只包含一个超球面的中心（可能更容易）。
在此类树中插入和删除实体很快，因此超球面改变大小只会导致一对删除/插入操作。（我怀疑如果球体变小，球体大小会通过局部附加递归分区发生变化，或者如果球体增长，则局部 K 块合并会改变球体大小）。
我没有和他们合作过，但你也可以考虑二进制空间分区。这些让您可以使用二叉树而不是 k 树来划分空间。我知道 KDTrees 是这种情况的一个特例。
但无论如何，我认为 2^K 树和/或 BSP/KDTrees 的插入/删除算法很好理解且速度很快。所以超球体大小的变化会导致删除/插入操作，但这些操作很快。所以我不明白你对 KD-trees 的反对意见。
我认为所有这些的表现都是渐近相同的。
我会为 SQLite 使用 R*Tree 扩展。一个表通常有 1 维或 2 维数据。SQL 查询可以组合多个表来进行更高维度的搜索。
负距离的公式有点奇怪。距离在几何中是正的，所以可能没有太多有用的理论可以使用。
仅使用正距离的不同公式可能会有所帮助。阅读有关双曲空间的信息。这可能有助于为描述距离的其他方式提供想法。