文献

J-GLOBAL ID：201402233556814160   整理番号：14A0161149

単純多角形内部の最短経路発見のためのメモリ調節可能アルゴリズム

An Adjustable Work Space Algorithm for Finding a Shortest Path in a Simple Polygon

著者 (4件)： 小長谷松雄 (北陸先端科学技術大学院大) ,  浅野哲夫 (北陸先端科学技術大学院大) ,  CHEONG Otfried (KAIST, KOR) ,  WON BAE Sang (Kyonggi Univ., KOR)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 113  号： 371(COMP2013 38-59)  ページ： 59-62  発行年： 2013年12月13日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 平面に与えられたn頂点の単純多角形に対し,内部の任意の2点間の最短経路を発見するメモリ調節可能アルゴリズムを提案する。この問題は,入力として与えられた単純多角形Pに対して,質問点として多角形内部に2点p,qが与えられた時,Pの内部を通りpからqへの距離最小の経路を報告することである。本稿で提案するメモリ調節可能アルゴリズムは,任意の作業領域のサイズsに対して正常に実行され,sの増加に従い計算時間が短縮されるという性質を持つ。ここで,sは作業領域のサイズを表すパラメータで,Ω(1)≦s≦O(n)とする。ただし,Pに対しO(n log n)時間の前処理を許すとする。(著者抄録)

シソーラス用語： *計算幾何学 ,  経路 ,  多角形 ,  作業空間 ,  *アルゴリズム ,  *経路探索 ,  計算量
準シソーラス用語： 最短経路 ,  *最短経路アルゴリズム

分類 (1件)： 数値計算  (JE02000J)

タイトルに関連する用語 (4件)： 多角形 ,  経路発見 ,  調節可能 ,  アルゴリズム