9

かなり予測不可能な移動/成長/縮小超球で満たされた k 次元の連続 (ユークリッド) 空間を考えると、特定の座標に最も近い表面を持つ超球を繰り返し見つける必要があります。いくつかの超球が私の座標から同じ距離にある場合、最大の超球が勝ちます。(ハイパースフィアの総数は、時間の経過とともに同じままであることが保証されています。)

私の最初の考えは、KDTreeを使用することでしたが、超球体の不均一なボリュームは考慮されません。そこでさらに調べたところ、BVH (Bounding Volume Hierarchies) とBIH (Bounding Interval Hierarchies) が見つかりました。少なくとも 2/3 次元空間では。しかし、BVH に関するかなりの情報とビジュアライゼーションが見つかりましたが、BIH に関する情報はほとんど見つかりませんでした。

私の基本的な要件は、ボリュームを考慮したk 次元の空間データ構造であり、構築が超高速(オフライン) であるか、不均衡がほとんどない動的なものです。

上記の私の要件を考えると、どのデータ構造を使用しますか? 私が言及しなかった他のものはありますか？

編集 1: 言及するのを忘れました: ハイパースフェアは (実際には非常に期待されている) オーバーラップすることができます!

編集 2:「距離」(特に「負の距離」) の代わりに、説明したメトリックがポイントのパワーにはるかによく一致するように見えます。

4

2 に答える 2

3

Kの次元のためにQuadTree/Octree/generalized to 2^K-treeがうまくいくと思います。これらは空間を再帰的に分割し、おそらく、K サブキューブ (分割が偶数でない場合は K 長方形ブリック) が超球を含まない場合、または分割によって分離されないような 1 つ以上の超球を含む場合に停止できます。または、単一の超球の中心を含む (おそらく簡単です)。

このようなツリーでのエンティティの挿入と削除は高速であるため、超球体のサイズを変更すると、削除と挿入のペアの操作が発生するだけです。(球が小さくなる場合はローカルの追加の再帰パーティションによって球のサイズが変化する場合、または球が大きくなる場合はローカルの K ブロックのマージによってこれを最適化できると思います)。

私はそれらを扱ったことはありませんが、binary space partitionsを検討することもできます。これらにより、k ツリーの代わりにバイナリ ツリーを使用して空間を分割できます。KDTree はこれの特殊なケースであることを理解しています。

しかし、いずれにせよ、2^K ツリーおよび/または BSP/KDTree の挿入/削除アルゴリズムはよく理解されており、高速であると思いました。そのため、ハイパースフィアのサイズを変更すると、削除/挿入操作が発生しますが、それらは高速です。ですから、KD ツリーに対するあなたの異議は理解できません。

これらすべてのパフォーマンスは漸近的に同じだと思います。

于 2012-06-07T12:38:10.437 に答える
0

SQLite には R*Tree 拡張機能を使用します。通常、テーブルには 1 次元または 2 次元のデータが含まれます。SQL クエリは、複数のテーブルを組み合わせて、より高い次元で検索できます。

距離が負の定式化は少し奇妙です。幾何学では距離は正であるため、使用する有用な理論はあまりないかもしれません。

正の距離のみを使用する別の定式化が役立つ場合があります。双曲空間について読んでください。これは、距離を表す他の方法のアイデアを提供するのに役立つかもしれません。

于 2012-06-11T20:33:02.223 に答える