| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2012-04-27 15:20 任意の作業領域で効率よく線分交差を列挙するアルゴリズム ○小長谷松雄・浅野哲夫（北陸先端大）  COMP2012-7 |
|
| 抄録 | （和） | 本論文では，平面上に与えられた$n$本の線分が与えられたとき，任意の サイズの作業領域を用いて，それらの線分間のすべての交点を報告する 効率の良いアルゴリズムを提案する．正確には，作業領域のサイズを表す パラメータ$s$の値が$O(1)$と$O(n)$の間で指定されたとき，提案アルゴリズムは， $O(\log n)$ビットの長さの$O(s)$個の語からなる作業領域を用いて，すべての 交点を ほぼ$O(n^2/\sqrt{s} + K)$の時間で列挙する．ただし，$K$は交差線分対の 総数である．また，入力の線分たちがある定数通りの傾きしかもたないときには， この計算時間を$O((n^2/s) \log s + K)$に改善できることも示す． |
| （英） | This paper presents an efficient algorithm for reporting all intersections among $n$ given line segments in the plane using work space of arbitrarily given size. More exactly, given a parameter $s$ which is between $O(1)$ and $O(n)$ specifying the size of work space, the algorithm reports all the segment intersections in roughly $O(n^2/\sqrt{s} + K)$ time using $O(s)$ words of $O(\log n)$ bits, where $K$ is the total number of intersecting pairs. The time complexity can be improved to $O((n^2/s) \log s + K)$ when input line segments have only some constant number of different slopes. |
|
| キーワード | （和） | 計算幾何学 / 作業領域サイズ調節可能アルゴリズム / 線分交差検出 / 線分交差列挙 / / / / |
| （英） | computational geometry / adjustable work space algorithm / segment intersection detection / segment intersection reporting / / / / | |
| 文献情報 | 信学技報, vol. 112, no. 21, COMP2012-7, pp. 45-52, 2012年4月. | |
| 資料番号 | COMP2012-7 | |
| 発行日 | 2012-04-20 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2012-7 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2012-04-27 - 2012-04-27 |
| 開催地（和） | 大阪府立大学 |
| 開催地（英） | Osaka Prefecture University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2012-04-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 任意の作業領域で効率よく線分交差を列挙するアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Algorithm for Reporting All Segment Intersections Using Work Space of Arbitrary Size |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 計算幾何学 / computational geometry |
| キーワード(2)（和/英） | 作業領域サイズ調節可能アルゴリズム / adjustable work space algorithm |
| キーワード(3)（和/英） | 線分交差検出 / segment intersection detection |
| キーワード(4)（和/英） | 線分交差列挙 / segment intersection reporting |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 小長谷 松雄 / Matsuo Konagaya / コナガヤ マツオ |
| 第1著者 所属（和/英） | 北陸先端科学技術大学院大学 (略称： 北陸先端大) Japan Advanced Institute of Science and Technology (略称： JAIST) |
| 第2著者 氏名（和/英/ヨミ） | 浅野 哲夫 / Tetsuo Asano / アサノ テツオ |
| 第2著者 所属（和/英） | 北陸先端科学技術大学院大学 (略称： 北陸先端大) Japan Advanced Institute of Science and Technology (略称： JAIST) |
| 講演者 | 第1著者 |
| 発表日時 | 2012-04-27 15:20:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2012-7 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | no.21 |
| ページ範囲 | pp.45-52 |
| ページ数 | 8 |
| 発行日 | 2012-04-20 (COMP) |
[研究会発表申込システムのトップページに戻る]