講演抄録/キーワード |
講演名 |
2010-10-15 10:05
幾何問題に対する定数作業領域アルゴリズム(2) ○浅野哲夫(北陸先端大)・Wolfgang Mulzer(Princeton Univ.)・Gunter Rote(Free Univ.)・Yajun Wang(マイクロソフト) COMP2010-32 |
抄録 |
(和) |
本報告では定数作業領域あるいは対数記憶領域と呼ばれる制約のある計算モデル上で効率よく実行できる幾何問題に対するアルゴリズムを提案する.本報告では,単純な多角形の内部に指定された任意の2点を結ぶ最短経路を求める効率のよい定数作業領域アルゴリズムを提案する.グラフ上での最短経路問題はNL-完全であることが証明されているが,多角形の内部に限定すれば2乗に比例する時間で解けることを示す. |
(英) |
We present space-efficient algorithms for geometric problems in a restricted computational model called ``constant work space'' or ``log-space'' computation. In this report we propose an efficient constant work space algorithm for finding a shortest path between two points in a simple $n$-gon. Although the shortest path problem in general graphs is NL-complete~\cite{tantau}, this constrained problem can be solved in quadratic time using only constant work space. |
キーワード |
(和) |
/ / / / / / / |
(英) |
constant-work-space algorithm / shortest path / simple polygon / simple path in a tree / / / / |
文献情報 |
信学技報, vol. 110, no. 232, COMP2010-32, pp. 9-15, 2010年10月. |
資料番号 |
COMP2010-32 |
発行日 |
2010-10-08 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2010-32 |