A Two-Dimensional Kinetic Triangulation with Near-Quadratic Topological Changes

Pankaj K. Agarwal, Yusu Wang and Hai Yu
Discrete and Computational Geometry
Volume 36, Number 4 / December, 2006
Pages 573-592
DOI 10.1007/s00454-006-1266-7

SoCG2004特集号から．

2次元点集合の三角形分割に対する運動データ構造 (kinetic data structure) の論文．
特に，三角形分割がグラフとして変化する回数 (トポロジー的変化) の上界とそれに関連するデータ構造 (およびアルゴリズム) を与えている．
点の軌道は各座標とも定数次数の多項式に従うとしている．
組合せ的変化 (点の削除，挿入，軌道の修正) は考えていない．

トポロジー的変化について知られている最良の上界はほぼ3次，下界は2次であった．
この論文では上界をほぼ2次に改善している．
データ構造としてはhierarchical fan triangulationという概念を導入してそれを用いている．
(保持する三角形分割はどんなものでもよいので，それをhierarchical fan triangulationに限定してるところが1つのポイントになっているようだ．)
それを用いて，各更新がO(log n)時間で行なえるようになっている．
データ構造は乱数を使用していて，トポロジー的変化は高確率でほぼ2次ということになっている．
どのように脱確率化 (derandomization) すればよいか，というのが未解決問題．