快速橢球面相交算法

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是維度 - 這就是它與這類事情一致的方式。