Loading article…
Jump-and-Walkは、三角形分割における点位置特定のためのアルゴリズムです(ただし、理論的な解析のほとんどは 2D および 3D ランダムDelaunay 三角形分割で行われました)。驚くべきことに、このアルゴリズムは、三角形分割自体の単純な表現を除いて、前処理や複雑なデータ構造を必要としません。Jump-and-Walk の前身は Lawson (1977) と Green および Sibson (1978) によるもので、ランダムな開始点 S を選択し、S からクエリ点 Q に向かって一度に 1 つの三角形ずつ移動します。しかし、これらの前身の理論的な解析は 1990 年代半ば以降まで知られていませんでした。
ジャンプアンドウォークは、少数のサンプル点を選択し、Q に最も近いサンプル点から、Q を含む単体が見つかるまでウォークを開始します。このアルゴリズムはしばらくの間、実務上の慣習として知られていましたが、1990 年代半ばに Devroye、Mucke、Zhu によって、2 次元ランダム Delaunay 三角形分割におけるアルゴリズムの正式な説明とパフォーマンスの分析が行われました (論文は Algorithmica、1998 年に掲載)。3 次元ランダム Delaunay 三角形分割の分析は、Mucke、Saias、Zhu によって行われました (ACM Symposium of Computational Geometry、1996 年)。どちらの場合も、境界条件が仮定されており、すなわち、Q はランダム Delaunay 三角形分割の頂点が描画される凸領域の境界からわずかに離れている必要があります。 2004年、Devroye、Lemaire、Moreauは、2次元では境界条件を撤回できることを示した（この論文は、Computational Geometry: Theory and Applications、2004年に掲載された）。
ジャンプ・アンド・ウォークは、QHULL、Triangle、CGALなど、多くの有名なソフトウェアパッケージで使用されています。