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