講演抄録/キーワード |
講演名 |
2016-09-06 14:30
二次元空間上の長方形領域による空間的近接パターン列挙について ○小笠原智明・今井 浩(東大)・喜田拓也(北大) COMP2016-19 |
抄録 |
(和) |
空間的に近接した点集合を空間的近接パターンと呼ぶ.空間的近接パターンを効率よく列挙する基礎研究として,1次元空間上において,幅が$m_1$の領域に含まれる点集合を列挙するアルゴリズムである尺取虫法(関根,宇野,有村,DEIM2012)が提案されている.尺取虫法は1次元空間上の与えられた$n$個の点に対して,左から右へ幅$m_1$の領域を動かすことで,その領域に含まれる点集合を$O(n)$時間,$O(n)$領域で列挙する.しかし,尺取虫法を$d$次元空間上へ拡張するにあたって,重複解を出力してしまうという問題点がある.そこで,本稿では,尺取虫法を2次元へ拡張する手法についての考察を行い,また尺取虫法とは異なる組み合わせ的なアプローチによる1次元上でのアルゴリズムを提案する. |
(英) |
(Not available yet) |
キーワード |
(和) |
列挙アルゴリズム / 計算幾何学 / / / / / / |
(英) |
/ / / / / / / |
文献情報 |
信学技報, vol. 116, no. 211, COMP2016-19, pp. 29-35, 2016年9月. |
資料番号 |
COMP2016-19 |
発行日 |
2016-08-30 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2016-19 |