抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
n頂点上のポリラインを与えられた場合,元のポリラインまでの距離が,いくつかの距離測度,通常,局所Hausdorffまたは局所Fr’echet距離の下で与えられた閾値にある新しいポリラインを定義する,これらの頂点の最小サイズサブシーケンスのためのポリライン単純化問題kasksが与えられた。ここでは,単純化ポリラインの各ラインセグメントに対して,元のポリラインにおける対応するサブ曲線までの距離のみを測定した。MelkmanとO’Rourke[Computational Moformation’88]は,O(n ̄2logn)時間における局所Hausdorff距離の下でのポリライン単純化を解くための幾何学的データ構造を導入し,そして,Guibas,Hershberger,Mitchell,およびSnoeyink[Int.J.Comput.Geom.Appl.’93]は,Fr’echet距離の下でのポリライン単純化を,規則化スタビングとして考慮し,そして,O(n ̄2log ̄2n)の実行時間を有するアルゴリズムを提供したが,しかし,それらは,元のポリラインの頂点だけを使用するために,単純化ポリラインを制限しなかった。著者らは,Imai-Iriアルゴリズムを適用するとき,O(n ̄3)の代わりにO(n ̄2logn)時間における局所Fr’echet距離の下でポリライン単純化を解くためにそれらの技術を調整することができることを示した。このアルゴリズムは,複数の他のアルゴリズムのためのより効率的なサブルーチンとして役立つ可能性がある。この定理を実証するために厳密な証明と同様に簡単なアルゴリズム記述を提供した。また,著者らは,MelkmanとO’Rourkeによって導入された幾何学的データ構造を調査して,それはより詳細に波面として言及して,いくつかの興味深い特性を特徴とした。その結果,L_1とL_∞ノルムの下で,このアルゴリズムは著しく単純化され,O(n ̄2)の実行時間のみを必要とすることを証明した。また,このアルゴリズムがユークリッドノルムL_2でもこの実行時間を常に達成するポリラインの自然クラスを定義する。【JST・京大機械翻訳】
