キネティックデータ構造（Kinetic Data Structure）とは？仕組みと証明書アプローチを解説

キネティックデータ構造は、計算幾何学の分野で生まれた概念であり、連続的に移動・変化する幾何学的システムの属性を追跡し続けるために設計されたデータ構造です。

基本概念

キネティックデータ構造は、時間とともに連続的に動き続ける幾何学的システムのある属性を追跡する目的で実装されます。代表的な例として、キネティック凸包データ構造が挙げられます。これは、n個の移動点からなる集合について、その凸包を常に追跡し続けるデータ構造です。

この考え方は、ロボット工学、アニメーション、コンピュータグラフィックスなどで求められる衝突検出や可視性判定といった、連続的に運動する物理的対象を扱う計算幾何学の問題に着想を得て発展しました。

概要：基本的な操作

キネティックデータ構造は、時間の関数として変化する値の集合を持つシステム上に実装されます。システム内の各値 v は v = f(t) の形で表され、現在の仮想時間 t における状態を問い合わせることができます。さらに、次の2つの基本操作が提供されます。

• advance(t): システムの状態を時刻 t まで進めます。
• change(v, f(t)): 現在時刻を起点として、値 v の今後の軌道（運動の関数）を f(t) に変更します。

用途に応じて追加の操作をサポートすることもできます。例えば、点の集合に対してキネティックデータ構造を実装する場合、点の挿入・削除も可能にするのが一般的です。

従来のデータ構造との違い

キネティックデータ構造の最大の特徴は、格納された値が時間とともに連続的に変化することを許容する点です。

原理的には、固定した時間間隔で各点の位置をサンプリングし、従来型の「静的な」データ構造から点を削除して再挿入し直すことでも同様の近似は可能です。しかし、この手法には以下のような問題があります。

• サンプリング間隔が長すぎると精度が落ちる（アンダーサンプリング）
• サンプリング間隔が短すぎると無駄な計算が増える（オーバーサンプリング）
• 削除と再挿入の繰り返しにより計算資源を大きく浪費する

キネティックデータ構造は、こうした非効率を避けつつ、常に正確な状態を維持することを目指しています。

証明書アプローチによる構築手法

キネティックデータ構造を実際に構築する際の一般的なアプローチとして、証明書（certificate）アプローチがあります。手順は以下の通りです。

1. 現状のデータ構造を保持する：現在時刻 t におけるシステムのデータ構造を保存し、現在の仮想時間に対する問い合わせを可能にします。
2. 証明書で補強する：データ構造を証明書で拡張します。証明書は「データ構造が正確であるための条件」を表し、現時点ではすべて真です。いずれかの証明書が偽になったときだけ、データ構造の正確性が損なわれます。
3. 失効時刻を計算する：各証明書について、真でなくなる時刻（失効時刻）を事前に計算します。
4. 優先度付きキューに登録する：証明書を失効時刻をキーとして優先度付きキューに格納します。
5. 時間を進める：時刻 t まで進むには、キュー内で最小の失効時刻を持つ証明書を確認します。その証明書が時刻 t より前に失効する場合は、キューから取り除き、失効した時点でデータ構造が再び正確になるよう修復し、関連する証明書を更新します。この処理を、最小の失効時刻を持つ証明書が時刻 t より後に失効するようになるまで繰り返します。そうなれば、時刻 t においてすべての証明書が真であると保証できるため、データ構造は時刻 t の問い合わせに正しく回答できます。

イベントの種類：内部イベントと外部イベント

証明書の失効は「イベント」と呼ばれます。イベントは、データ構造が維持している性質に影響を与えるかどうかで次のように分類されます。

• 内部イベント：イベント発生時点で、データ構造が維持している属性そのものは変化しないイベント。
• 外部イベント：イベント発生時点で、データ構造が維持している属性が実際に変化するイベント。

性能評価の4つの指標

証明書アプローチでキネティックデータ構造を評価する際には、主に次の4つの性能指標が用いられます。ここで「小さい」とは、その量が n の多対数関数であるか、十分小さな ε に対して O(n^ε) であることを意味し、n は対象となるオブジェクトの数です。

• 応答性：証明書が失敗した後、データ構造を修復するのにかかる時間。
• 局所性：1つのオブジェクトが関与する証明書の最大数。少ないほど並列化や分散処理に適します。
• 緊湊性：任意の時点で保持される証明書の総数。少ないほどメモリ効率が良いことを示します。
• 効率性：発生した内部イベントの数と、実際に追跡対象の属性が変化した回数の比率。

これらの指標をバランスよく満たすことが、実用的なキネティックデータ構造の設計において重要となります。