直線多角形領域における直線リンク直径と半径【JST・京大機械翻訳】

Arseneva Elena; Chiu Man-Kwun; Korman Matias; Markovic Aleksandar; Okamoto Yoshio; Ooms Aurelien; van Renssen Andre; Roeloffzen Marcel

プレプリント

J-GLOBAL ID：202202204410843713 整理番号：22P0043354

直線多角形領域における直線リンク直径と半径【JST・京大機械翻訳】

Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain

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

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

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

n頂点とhホールの直線多角形ドメイン内の直線リンク距離の下での直径と半径の計算を研究した。ドメインの点の対間の距離を符号化する配向距離のグラフを導入した。これにより,この問題を変換し,候補をより効率的に探索できる。著者らのアルゴリズムは,最小{O(n ̄ω),O(n ̄2+nhlogh+χ ̄2)}時間における直径と半径の両方を計算し,そこでは,ω<2.373が行列乗算指数とΔΨ(n)||O(n ̄2)が配向距離のグラフのエッジの数であることを示した。また,O(n ̄2logn)時間で動作する直径を計算するための高速アルゴリズムを提供した。【JST・京大機械翻訳】

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

グラフ理論基礎

, , , ,

前のページに戻る