(連続)Fr’echet距離の近似【JST・京大機械翻訳】

Colombe Connor; Fox Kyle

プレプリント

J-GLOBAL ID：202202221088853084 整理番号：21P0039908

(連続)Fr’echet距離の近似【JST・京大機械翻訳】

Approximating the (Continuous) Fr\'echet Distance

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2020年07月15日プレプリントサーバーでの情報更新日： 2021年03月27日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

2つの多角形鎖間のFr’echet距離を近似的に計算するために,サブ指数近似比を有する初めての強い二次時間アルゴリズムを記述した。特に,letPおよびQは,d次元Euclid空間においてn頂点を有する2つの多角形鎖であり,そして,α→π[√n,n]であった。著者らのアルゴリズムは,時間O((n ̄3/α ̄2)logn)におけるO(α)近似Fr’echet対応を決定論的に見つける。特に,ほぼ線形のO(nlogn)時間でのO(n)近似を得て,以前に最良の知る結果,線形時間2 ̄O(n)近似に対する大きな改善を得た。著者らのアルゴリズムの一部として,著者らはまた,近似比が任意に小さい定数因子まで同じである近似最適化アルゴリズムへのFr’echet距離に対する任意の近似決定手順をどのように変えるかを述べた。近似最適化アルゴリズムへの変換は,O(logn)因子だけによる決定手順の実行時間を増加させる。【JST・京大機械翻訳】

, , , ,
, , 【Automatic Indexing@JST】

計算理論 , グラフ理論基礎 , 数値計算

前のページに戻る