快速椭圆体交叉算法

Question

假设我有100万个任意形状,任意定向的N维椭圆体随机散布在N维空间中.给定一组子椭圆体,我想"快速"确定第一组椭圆体相交的所有椭球的集合.

必须有一个算法.它是什么？什么是"O"复杂性？

Answer 1

如果您允许N维数据,则"O"复杂性会受到维数灾难的影响.(有关详细信息,请参阅此维基百科文章).我建议借用物理模拟并将这个问题分为"广泛阶段"和狭窄阶段:

• 宽阶段保守地发现可能重叠的椭圆对的极小组.
• 窄相将一组可能重叠的椭圆修剪为实际重叠的那对.

窄阶段是测试任意椭圆之间的交叉的直接计算几何问题.对于广义阶段,您需要使用空间结构,例如空间散列,空间树(R树,Kd树,X树,UB树等等),或者给定ad-hoc结构您正在加载的数据的某些特殊属性(例如不平衡树或散列).

目前流行的方法是Kd树.有很多文档和已经编码的Kd树版本可以很容易地配置,所以我建议你在线查看.(谷歌是你的朋友.)使用大多数树结构的优点是,如果设置你正在寻找相对紧凑的交叉点,你只能在树中搜索一次并找到交叉点而不必执行多个树遍历.这将有助于缓存(无论是来自主内存还是磁盘)访问模式.相同的算法可以处理不同的成员查询.但是,您可能正在做的工作将从紧凑的查询集属性中受益匪浅.

Kd树不会修复所有椭球的问题 - 例如,如果你有一个尺寸为N的椭球,其主轴是从(0,0,0,0,...)到(1,1), 1,1,......)但是具有小的或无关紧要的次轴(并且此后不相交很多)仍然需要是在所有N维​​中覆盖[0,1]的节点.如果您的椭圆体落在[0,1] ^ n中,那么每个椭圆体将测试与上述不方便的椭圆体的交点.然而,对于真实世界的数据(甚至大多数合成数据,除非你真的努力使Kd树变慢),Kd树方法应该是一个胜利.

如果你期望Kd-tree成为千维椭球的成功,那么你可能会更好地进行强力搜索.(前面提到的维数诅咒.)但是......

如果你有一个优化的实现,那么一百万个条目也不算太糟糕,但是如果你做了很多查询(数百万),它将会很慢(大约10秒或更差).然而,我已经看到一些令人惊讶的数字来自经过优化的矢量化代码.(甚至使用这种策略运送了一些产品.)通过正确的缓存一致性,强制执行最多只需要几毫秒.这意味着在C/C++中使用ASM或矢量内在函数 - 不确定您正在使用哪种语言.

对于大多数数据,O复杂度(忽略维数的诅咒)应该是关于查询的摊销O(m log n)(一旦构建了树),其中m是查询集中的省略号,n是省略号的数量在数据集中.构建数据本身不应该比O(n log n)差.将所有内容乘以Exp(d),其中d是维度 - 这就是它与这种事物的关系.