快速椭球面相交算法

Question

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

这需要一个算法。它是什么？什么是“O”复杂性？

Answer 1

如果您允许使用N维数据，则“O”复杂度会受到维度的诅咒的影响。 （有关更多信息，请参阅this wikipedia article）。我建议借用物理模拟并将此问题划分为“宽广阶段”和“窄阶段”：

• 宽广阶段保守地发现潜在重叠椭圆对的极小组集合。
• 窄阶段将可能重叠的椭圆对集合修剪为实际重叠的那些对。

窄阶段是测试任意椭圆之间相交的直接计算几何问题。对于广义阶段，您将希望使用空间结构，如空间散列，空间树（R树，Kd树，X树，UB树等）或给定的特定结构您正在加载的数据的一些特殊属性（如不平衡的树或散列）。

当前流行的方法是Kd树。有许多文档和Kd-tree的已编码版本可以很容易配置，所以我建议你看一下在线。 （Google是你的朋友）使用大多数树结构的好处是，如果设置你正在寻找十字路口是相对紧凑的，你可以只搜索一次树并找到交叉点，而不必执行多次树遍历。这将有助于缓存（来自主内存或磁盘）访问模式。相同的算法可以处理不同的元素查询。但是，您可能会从紧凑查询集属性中获益良多。

Kd-tree不会解决所有椭球的问题 - 例如，如果您有一个尺寸为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是维度 - 这就是它与这类事情一致的方式。