假设我有一百万个任意形状，任意方向的n维椭球随机分布在n维空间中。给定一个子椭球体集，我想“快速”确定第一个椭球体集与之相交的所有椭球体集。
必须有一个算法。它是什么？什么是“O”复杂性？
最佳答案
如果你允许n维数据，那么“O”复杂度会受到维数灾难的影响。（详见this wikipedia article）。我建议借鉴物理模拟，把这个问题分为“宽阶段”和“窄阶段”：
宽相位保守地发现了更小的一组可能重叠的椭圆。
窄相位将一组潜在重叠的椭圆对修剪为那些实际重叠的椭圆对。
窄相位是检验任意椭圆相交的一个简单的计算几何问题。对于广泛的阶段，您将希望使用空间结构，如空间哈希、空间树（r-tree、kd-tree、x-tree、ub-tree等），或者考虑到要加载的数据的某些特殊属性（如不平衡树或哈希），使用特殊结构。
目前流行的方法是kd树。有很多文档和kd树的已经编码的版本是可以配置的，所以我建议您在线查看。（google是你在这方面的朋友）使用大多数树结构的优点是，如果你要寻找的交集相对紧凑，你可以只在树中搜索一次，找到交集，而不必执行多个树遍历。这将有助于缓存（无论是从主内存还是磁盘）访问模式。同样的算法可以处理不同成员的查询。不过，您所做的工作很可能会从压缩查询集属性中受益匪浅。
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 logn）差。把所有的东西乘以exp（d），其中d是维，这就是它处理这类事情的方式。