Reg*_*ent 9 c spatial multidimensional-array data-structures
给定k维连续(欧几里德)空间充满了相当不可预测的移动/生长/收缩的超球面,我需要重复找到其表面最接近给定坐标的超球面.如果一些超球面与我的坐标距离相同,那么最大的超球面会获胜.(随着时间的推移,超球面的总数保证保持不变.)
我的第一个想法是使用KDTree,但它不会考虑超球体的非均匀体积.所以我进一步观察并找到了BVH(边界体积层次结构)和BIH(边界间隔层次结构),这似乎可以解决问题.至少在二维/三维空间中.然而,虽然在BVH上找到了相当多的信息和可视化,但我几乎找不到任何关于BIH的信息.
我的基本要求是k维空间数据结构,它考虑了体积,要么是超级快速构建(离线),要么是动态的,几乎没有任何不平衡.
鉴于我的上述要求,您会使用哪种数据结构？我还没提到的其他任何一个？
编辑1:忘记提及:允许hypershperes(实际上是高度期望的)重叠!
我希望四叉树/八叉树/广义为 2^K 树对于 K 的维数可以解决问题；这些递归地划分空间，并且当 K 子立方体（或 K 矩形砖，如果分割不均匀）不包含超球体，或包含一个或多个超球体时，您可以停止，这样分区不会分离任何超球体，或者仅包含单个超球面的中心（可能更容易）。
在此类树中插入和删除实体的速度很快，因此超球面改变大小只会导致删除/插入操作对。（我怀疑如果你的球体大小通过本地附加递归分区（如果球体变小）或本地 K 块合并（如果球体增长）发生变化，则可以对此进行优化。
我没有使用过它们，但您也可以考虑二进制空间分区。这些允许您使用二叉树而不是 k 树来划分空间。我知道 KDTree 是一个特例。
但无论如何，我认为 2^K 树和/或 BSP/KDTree 的插入/删除算法很好理解并且速度很快。因此，超球面大小的变化会导致删除/插入操作，但速度很快。所以我不明白你对 KD 树的反对。
我认为所有这些的表现都是渐近相同的。
| 归档时间： |
|
| 查看次数： |
934 次 |
| 最近记录： |