お知らせ 2023年度・2024年度 学生員 会費割引キャンペーン実施中です
お知らせ 技術研究報告と和文論文誌Cの同時投稿施策(掲載料1割引き)について
お知らせ 電子情報通信学会における研究会開催について
お知らせ NEW 参加費の返金について
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2010-10-15 10:05
幾何問題に対する定数作業領域アルゴリズム(2)
浅野哲夫北陸先端大)・Wolfgang MulzerPrinceton Univ.)・Gunter RoteFree 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

研究会情報
研究会 COMP  
開催期間 2010-10-15 - 2010-10-15 
開催地(和) 東北大学 
開催地(英) Tohoku Univ. 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2010-10-COMP 
本文の言語 英語(日本語タイトルあり) 
タイトル(和) 幾何問題に対する定数作業領域アルゴリズム(2) 
サブタイトル(和)  
タイトル(英) Constant-Work-Space Algorithms for Geometric Problems(2) 
サブタイトル(英)  
キーワード(1)(和/英) / constant-work-space algorithm  
キーワード(2)(和/英) / shortest path  
キーワード(3)(和/英) / simple polygon  
キーワード(4)(和/英) / simple path in a tree  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 浅野 哲夫 / Tetsuo Asano / アサノ テツオ
第1著者 所属(和/英) 北陸先端科学技術大学院大学 (略称: 北陸先端大)
JAIST (略称: JAIST)
第2著者 氏名(和/英/ヨミ) Wolfgang Mulzer / Wolfgang Mulzer /
第2著者 所属(和/英) Princeton University (略称: Princeton Univ.)
Princeton University (略称: Princeton Univ.)
第3著者 氏名(和/英/ヨミ) Gunter Rote / Gunter Rote /
第3著者 所属(和/英) Free University (略称: Free Univ.)
Free University (略称: Free Univ.)
第4著者 氏名(和/英/ヨミ) Yajun Wang / Yajun Wang /
第4著者 所属(和/英) Microsoft Research (略称: マイクロソフト)
Microsoft Research (略称: Microsoft)
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者 第1著者 
発表日時 2010-10-15 10:05:00 
発表時間 35分 
申込先研究会 COMP 
資料番号 COMP2010-32 
巻番号(vol) vol.110 
号番号(no) no.232 
ページ範囲 pp.9-15 
ページ数
発行日 2010-10-08 (COMP) 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会