電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2012-06-21 16:20
包含多角形列の計算手法とその実験的解析
大西建輔東海大)・星 守電通大COMP2012-23
抄録 (和) 我々はこれまで包含多角形列の計算手法について研究をおこなってきた. 前の論文で, 凸多角形に対する2つの手法: 最適法と貪欲法という構成法を提案した. 前者は最適なk 多角形を順に計算するものであり, 後者は最適に近いk 多角形(k >=
5 の場合) を省メモリで高速に計算する手法であった.
本稿では, 単純多角形に対する包含多角形列の計算手法: ナイーブ法とポケット法について述べる. これらの手法は, 以前の研究でよい性能をあげた貪欲法を元にしたものであり, これらの手法の最悪計算量は, n 頂点を持つ単純多角形の場合,O(n^2) 時間とO(n) 領域である. ポケット法は平均時間計算量の解析ができ, 単純多角形の頂点が正方形領域から一様に選ばれた場合はO(n^2/log n) 時間であり, 円盤領域から選ばれた場合はO(n^{5/3}) 時間であること示す. また, これらの手法を実装し, 単純多角形の集合に適用したところ, ナイーブ法はO(n^2) 時間, ポケット法はO(n^2/log n) 時間(正方形領域), O(n^{5/3}) 時間(円盤領域) となったことについても述べる. 
(英) We have studied algorithm for computing a sequence of circumscribing polygons. In our previous paper, we proposed two constructive methods for convex polygon: optimal and greedy. The former computes the smallest k-gons, the latter quickly computes nearly smallest k-gons with small memory for k >= 5.
In this paper, we propose two methods for computing a sequence of polygons circumscribing a given simple polygon which is more general rather than convex. Since the previous paper showed the greedy method is fairly good, we propose two methods based on the greedy method, called naive method and pocket method. The computation complexity of two methods is O(n^2) time and O(n) space in the worst case for a simple polygon with n vertices. The pocket method is done in O(n^2/log n) time for points selected from square region and O(n^{5/3}) time for that from disk region on average.
Moreover, we apply the methods to sets of simple polygons. The execution time of the naive method and that of the pocket methods are O(n^2), O(n^2/ log n) for square region and O(n^{5/3}) for disk region, respectively.
キーワード (和) 単純多角形 / 包含多角形 / 形状による検索 / / / / /  
(英) simple polygon / circumscribing polygon / retrieval by shape / / / / /  
文献情報 信学技報, vol. 112, no. 93, COMP2012-23, pp. 87-93, 2012年6月.
資料番号 COMP2012-23 
発行日 2012-06-14 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380
著作権に
ついて
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034)
PDFダウンロード COMP2012-23

研究会情報
研究会 COMP  
開催期間 2012-06-21 - 2012-06-21 
開催地(和) 北海道大学 
開催地(英) Hokkaido University 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2012-06-COMP 
本文の言語 日本語 
タイトル(和) 包含多角形列の計算手法とその実験的解析 
サブタイトル(和)  
タイトル(英) A method for computing a sequence of circumscribing polygons 
サブタイトル(英)  
キーワード(1)(和/英) 単純多角形 / simple polygon  
キーワード(2)(和/英) 包含多角形 / circumscribing polygon  
キーワード(3)(和/英) 形状による検索 / retrieval by shape  
キーワード(4)(和/英) /  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 大西 建輔 / Kensuke Onishi / オオニシ ケンスケ
第1著者 所属(和/英) 東海大学 (略称: 東海大)
Tokai University (略称: Tokai Univ.)
第2著者 氏名(和/英/ヨミ) 星 守 / Mamoru Hoshi /
第2著者 所属(和/英) 電気通信大学 (略称: 電通大)
The University of Electro-Communications (略称: UEC)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第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著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2012-06-21 16:20:00 
発表時間 25 
申込先研究会 COMP 
資料番号 IEICE-COMP2012-23 
巻番号(vol) IEICE-112 
号番号(no) no.93 
ページ範囲 pp.87-93 
ページ数 IEICE-7 
発行日 IEICE-COMP-2012-06-14 


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

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


IEICE / 電子情報通信学会