キネティックデータ構造

運動データ構造は、連続的に移動する幾何学システムの属性を追跡するために使用されるデータ構造です。 ^{[1] [2] [3] [4]} たとえば、運動凸包データ構造は、移動する点のグループの凸包を維持します。運動データ構造の開発は、ロボット工学、アニメーション、コンピュータグラフィックスでの衝突や可視性の検出など、連続的に移動する物理オブジェクトを含む計算幾何学の問題によって促進されました。 ${\displaystyle n}$

キネティック データ構造は、既知の方法で時間の関数として変化する一連の値が存在するシステムで使用されます。したがって、システムにはいくつかの値があり、各値 に対して であることがわかっています。キネティック データ構造により、現在の仮想時間 におけるシステムに対するクエリと、2 つの追加操作 が可能になります。${\displaystyle v}$${\displaystyle v=f(t)}$${\displaystyle t}$

• ${\displaystyle {\textrm {前進}}(t)}$: システムを時間 まで進めます。${\displaystyle t}$
• ${\displaystyle {\textrm {変化}}(v,f(t))}$:現在の時刻における値の軌道を に変更します。${\displaystyle v}$${\displaystyle f(t)}$

追加の操作がサポートされる場合もあります。たとえば、キネティック データ構造は、多くの場合、ポイントのセットで使用されます。この場合、構造では通常、ポイントの挿入と削除が可能です。

キネティック データ構造では、そこに保存された値が時間とともに連続的に変化します。原理的には、一定の時間間隔でポイントの位置をサンプリングし、各ポイントを削除して「静的」(従来の) データ構造に再挿入することで、これを近似できます。ただし、このようなアプローチは、使用される時間間隔に応じて、オーバーサンプリングまたはアンダーサンプリングの影響を受けやすく、計算リソースを無駄にする可能性があります。

運動データ構造を構築するには、次のような一般的なアプローチを使用することができる。^[5]

1. 現在の時刻のデータ構造をシステムに保存します。このデータ構造により、現在の仮想時刻でシステムに対してクエリを実行できます。${\displaystyle t}$
2. データ構造を証明書で補強します。証明書は、データ構造が正確である条件です。証明書はすべて現在正しいものであり、証明書の 1 つが正確​​でなくなった場合にのみ、データ構造は正確でなくなります。
3. 各証明書の失敗時間、つまり証明書が無効になる時間を計算します。
4. 証明書を失敗回数に応じて優先キューに保存する
5. 時間 に進むには、優先キューから失敗時間が最短の証明書を調べます。証明書が時間 より前に失敗した場合は、キューから取り出して、失敗時に正確になるようにデータ構造を修正し、証明書を更新します。優先キューで失敗時間が最短の証明書が時間 より後に失敗するまで、これを繰り返します。優先キューで失敗時間が最短の証明書が時間 より後に失敗した場合は、すべての証明書が時間 に true であるため、データ構造は時間 にクエリに正しく応答できます。${\displaystyle t}$${\displaystyle t}$${\displaystyle t}$${\displaystyle t}$${\displaystyle t}$${\displaystyle t}$

証明書の失敗は「イベント」と呼ばれます。イベントが発生したときにキネティック データ構造によって維持されるプロパティが変更されない場合、イベントは内部イベントと見なされます。イベントが発生したときにデータ構造によって維持されるプロパティが変更される場合は、イベントは外部イベントと見なされます。

証明書アプローチを使用する場合、パフォーマンスの尺度は 4 つあります。の多重対数関数である場合、または が任意に小さい （はオブジェクトの数）で ある場合、量は小さいと言えます。${\displaystyle n}$${\displaystyle O(n^{\epsilon })}$${\displaystyle \epsilon }$${\displaystyle n}$

応答性とは、証明書が失敗した場合にデータ構造を修正し、証明書を増強するために必要な最悪の時間です。更新に必要な最悪の時間が短い場合、キネティック データ構造は応答性が高いと言えます。

1 つの値が関与する証明書の最大数。移動するポイントを含む構造の場合、これは 1 つのポイントが関与する証明書の最大数です。1 つの値が関与する証明書の最大数が小さい場合、キネティック データ構造はローカルです。

データ構造をいつでも拡張するために使用される証明書の最大数。キネティック データ構造は、使用する証明書の数がまたは で、任意の小さい の場合にコンパクトです。(線形空間よりも小さい係数) ${\displaystyle O(n\operatorname {polylog} n)}$${\displaystyle O(n^{1+\epsilon })}$${\displaystyle \epsilon }$

構造が に進められるときに発生する可能性のある最悪のイベント数と、データ構造に対する「必要な変更」の最悪の数との比率。「必要な変更」の定義は問題によって異なります。たとえば、一連の移動点の運動殻を維持する運動データ構造の場合、必要な変更の数は、時間が に進められるにつれて運動殻が変化する回数になります 。この比率が小さい場合、運動データ構造は効率的であると言えます。 ${\displaystyle t=\infty}$${\displaystyle t=\infty}$

特定の運動データ構造のパフォーマンスは、特定の種類の軌道に対して分析できます。通常、次の種類の軌道が考慮されます。

• アフィン:(線形関数)${\displaystyle f(t)=at+b}$
• 有界次数代数:(有界次数の多項式関数)ある固定された に対して。${\displaystyle f(t)=\sum _{i=0}^{n}a_{i}t^{i}}$${\displaystyle n}$
• 疑似代数的: 関心のある証明書が真の時間と偽の 時間の間を反転するような軌跡。${\displaystyle O(1)}$

• キネティックトーナメント
• キネティックソートリスト
• キネティックヒープ
• 運動凸包
• 運動学的に最も近いペア
• 運動最小全域木
• 運動ユークリッド最小全域木