講演抄録/キーワード |
講演名 |
2013-12-21 09:30
単純多角形内部の最短経路発見のためのメモリ調節可能アルゴリズム ○小長谷松雄・浅野哲夫(北陸先端大)・Otfried Cheong(KAIST)・Sang Won Bae(Kyonggi Univ.) COMP2013-48 |
抄録 |
(和) |
平面に与えられた$n$頂点の単純多角形に対し,
内部の任意の2点間の最短経路を発見するメモリ調節可能アルゴリズムを提案する.
この問題は,入力として与えられた単純多角形$P$に対して,
質問点として多角形内部に2点$p,q$が与えられた時,
$P$の内部を通り$p$から$q$への距離最小の経路を報告することである.
本稿で提案するメモリ調節可能アルゴリズムは,
任意の作業領域のサイズ$s$に対して正常に実行され,
$s$の増加に従い計算時間が短縮されるという性質を持つ.
ここで,$s$は作業領域のサイズを表すパラメータで,$Omega(1) le s le O(n)$とする.
ただし,$P$に対し$O(nlog n)$時間の前処理を許すとする. |
(英) |
Given a simple polygon with $n$ vertices in a plane,
we compute the shortest path between two query points using less work space.
To solve the problem, in this paper,
we present an algorithm using only $O(s)$ work space, where $s$ is a parameter of the
size of the work space between $Omega(1)$ and $O(n)$.
Once the algorithm preprocesses an input of a simple polygon in $O(nlog n)$ time,
it can be compute with any size of the work space and can speed up as $s$ gets more work space. |
キーワード |
(和) |
計算幾何学 / 最短経路 / 作業領域調節可能アルゴリズム / / / / / |
(英) |
computational geometry / shortest path / adjustable work space / / / / / |
文献情報 |
信学技報, vol. 113, no. 371, COMP2013-48, pp. 59-62, 2013年12月. |
資料番号 |
COMP2013-48 |
発行日 |
2013-12-13 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2013-48 |