高速楕円体交点アルゴリズム

Question

仮に、N次元空間にランダムに散らばっている、任意に形状付けられた任意の向きのN次元楕円体が100万個あるとしましょう。サブセットの楕円体が与えられた場合、最初のセットからの楕円体が交差するすべての楕円体の集合を「迅速に」決定したいと思います。

このためのアルゴリズムが必要です。それは何ですか？ "O"の複雑さは何ですか？

Answer 1

N次元データを許可している場合、 "O"の複雑さは次元の呪いのに悩まされます。 （詳細については、this wikipedia articleを参照してください）。私は、物理シミュレーションからの借入と「広義の相」と狭い相にこの問題を分割お勧めします。

• 幅広い相は保守的に潜在的に楕円を重ねるのペアの大幅小さなセットを見つけました。
• 狭い位相は、潜在的に重なり合う楕円の組を、実際に重なり合う組に裁断する。

狭い位相は、任意の楕円間の交差をテストする簡単な計算上のジオメトリの問題です。幅広い段階では、空間ハッシュ、空間ツリー（Rツリー、Kツリー、Xツリー、UBツリーなど）、またはアドホック構造などの空間構造を使用したいと考えていますロードしているデータのいくつかの特殊なプロパティ（アンバランスなツリーやハッシュなど）

現在の一般的な方法はKdツリーです。すぐに設定可能な多くのドキュメントやすでにコーディングされたKdツリーのバージョンがあるので、オンラインで見ることをお勧めします。 （Googleはあなたの友人です）ほとんどのツリー構造を使用する利点は、比較的コンパクトな交差を探している場合は、ツリーを一度しか検索せず、複数のツリートラバーサルを実行しなくても交差を見つけることができるということです。これは、キャッシュ（メインメモリまたはディスクからのアクセス）のアクセスパターンに役立ちます。同じアルゴリズムは、異種のメンバークエリーを扱うことができます。ただし、コンパクトなクエリー・セット・プロパティーのメリットが大きいと思われる作業を行っている可能性があります。

Kdツリーはすべての楕円体について問題を解決しません。たとえば、主軸が（0、0、0、0、...）から（N）の楕円体の場合、小さい）または重要ではない第2の軸（および以後はあまり交差しない）を使用して、すべてのN次元で[0,1]をカバーするaノードである必要があります。あなたの楕円体が[0,1]^nに入ると、すべての楕円体は上記の不都合な楕円体との交差をテストします。しかし、実世界のデータ（そしてKdツリーの作成に熱心に努力しているのでなければほとんどの場合）では、Kdツリーのアプローチが勝つはずです。

千次元の楕円体でKd-treeが成功すると予想される場合は、無差別に検索する方がよいでしょう。しかし、...

もしあなたが最適化された実装を持っていれば100万のエントリはそれほど悪くはありませんが、たくさんのクエリを実行しているならば遅い（10秒程度かそれ以下）。しかし、最適化されたベクトル化されたコードから驚くべき数が出てきているのを見てきました。 （この戦略を使っていくつかの製品を出荷しただけでも）適切なキャッシュコヒーレンシで、ブルートフォースはたかだか数ミリ秒しかかかりません。

大部分のデータでは、複雑さは、次元数の呪縛を無視して、償却されたO（m log n）程度でなければなりません。これは、C/C++のASMまたはベクトル組み込み関数のいずれかを意味します。 （ツリーが構築されると）クエリの場合、mはクエリセット内の楕円の数であり、nはデータセット内の楕円の数です。データそのものを構築するのは、O（n log n）よりも悪いはずがありません。 Exp（d）ですべてを掛けます。ここで、dは次元です - これはこのようなことです。