Jump-and-Walk algorithm とは

Jump-and-Walkは、三角測量におけるポイント位置のアルゴリズムです(理論的解析のほとんどは、2Dおよび3DのランダムなDelaunay三角測量で実行されましたが)。驚くべきことに、このアルゴリズムは、三角形分割自体の単純な表現を除いて、前処理または複雑なデータ構造を必要としない。 Jump-and-Walkの前身は、Lawson(1977)とGreen and Sibson(1978)によるもので、ランダムな出発点Sを選んだ後、一度にSから問合せ点Qに向かって歩いていく。しかし、1990年代半ばまで、これらの先人たちの理論的分析は知られていなかった。
ジャンプ・アンド・ウォークは、サンプル・ポイントの小さなグループを選択し、Qを含むシンプレックスが見つかるまで、Qに最も近いサンプル・ポイントからウォークを開始する。このアルゴリズムは実際には民間伝承であり、アルゴリズムの正式な提示と2Dランダムドローネ三角測量におけるその性能の分析は、1990年代半ばのDevroye、Mucke、Zhuによって行われた(Algorithmica、1998に掲載された) 。 3Dランダムドローネ三角測量の分析は、Mucke、Saias、Zhu(ACM Symposium of Computational Geometry、1996)によって行われました。いずれの場合も、境界条件が仮定された。すなわち、Qは、ランダムドローネ三角形分割の頂点が描画される凸領域の境界からわずかに離れていなければならない。 2004年、Devroye、Lemaire、Moreauは、2Dで境界条件を取り除くことができることを示した(Computational Geometry:Theory and Applications、2004に掲載された)。
Jump-and-Walkは、QHULL、Triangle、CGALなどの多くの有名なソフトウェアパッケージで使用されています。