| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2007-11-22 13:25 O-Treeを拡張したレクトリニア多角形パッキング手法の高速化 ○浮邉英彦・藤吉邦洋（東京農工大）  VLD2007-96 DC2007-51 |
|
| 抄録 | （和） | レイアウトの再利用のため、 レクトリニア多角形をパッキングできることが望まれている。 そこで、 矩形だけのパッキングを効率よく表現するO-Treeの制約を拡張することで、 レクトリニア多角形パッキングを表現する方法が提案され、 その拡張された制約に基づいたO-Treeから、 部分矩形数を$n$、単純な矩形を含む多角形数を$m$として、 $O(nm)$時間でレクトリニア多角形パッキングを得るデコード手法が提案された。 本稿ではこのデコード手法を改良し、 部分矩形数を$n$、凹多角形数を$c$として、 計算複雑度を$O(n(c+1))$に高速化したデコード手法を提案する。 そして計算機実験により、その有効性を示す。 |
| （英） | In this paper, we propose an improved method to represent rectilinear block packing based on an expanded O-Tree. Here, each rectilinear block is partitioned into rectangle sub-blocks. Also, we propose a decode algorithm to obtain a rectilinear block packing in $O((c+1)n)$ time, where $n$ and $c$ each is the number of rectangle sub-blocks and concave blocks. The proposed algorithm requires $O(n)$ time if $c$ is constant. The effectiveness of the proposed method was confirmed by the experimental comparison. |
|
| キーワード | （和） | O-Tree / レクトリニア多角形 / パッキング / 凸多角形 / 凹多角形 / / / |
| （英） | O-Tree / rectilinear block / packing / convex block / concave block / / / | |
| 文献情報 | 信学技報, vol. 107, no. 336, VLD2007-96, pp. 43-48, 2007年11月. | |
| 資料番号 | VLD2007-96 | |
| 発行日 | 2007-11-15 (VLD, DC) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | VLD2007-96 DC2007-51 |
|
| 研究会情報 | |
| 研究会 | VLD CPSY RECONF DC IPSJ-SLDM IPSJ-ARC |
| 開催期間 | 2007-11-20 - 2007-11-22 |
| 開催地（和） | 北九州国際会議場 |
| 開催地（英） | Kitakyushu International Conference Center |
| テーマ（和） | デザインガイア2007 ―VLSI設計の新しい大地を考える研究会― |
| テーマ（英） | Design Gaia 2007 ---A New Frontier in VLSI Design--- |
| 講演論文情報の詳細 | |
| 申込み研究会 | VLD |
| 会議コード | 2007-11-VLD-CPSY-RECONF-DC-IPSJ-SLDM-IPSJ-ARC |
| 本文の言語 | 日本語 |
| タイトル（和） | O-Treeを拡張したレクトリニア多角形パッキング手法の高速化 |
| サブタイトル（和） | |
| タイトル（英） | Improved Method of Rectilinear Block Packing Based on O-Tree Representation |
| サブタイトル（英） | |
| キーワード(1)（和/英） | O-Tree / O-Tree |
| キーワード(2)（和/英） | レクトリニア多角形 / rectilinear block |
| キーワード(3)（和/英） | パッキング / packing |
| キーワード(4)（和/英） | 凸多角形 / convex block |
| キーワード(5)（和/英） | 凹多角形 / concave block |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 浮邉 英彦 / Hidehiko Ukibe / ウキベ ヒデヒコ |
| 第1著者 所属（和/英） | 東京農工大学 (略称： 東京農工大) Tokyo University of Agriculture and Technology (略称： TUAT) |
| 第2著者 氏名（和/英/ヨミ） | 藤吉 邦洋 / Kunihiro Fujiyoshi / フジヨシ クニヒロ |
| 第2著者 所属（和/英） | 東京農工大学 (略称： 東京農工大) Tokyo University of Agriculture and Technology (略称： TUAT) |
| 講演者 | 第1著者 |
| 発表日時 | 2007-11-22 13:25:00 |
| 発表時間 | 25分 |
| 申込先研究会 | VLD |
| 資料番号 | VLD2007-96, DC2007-51 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | no.336(VLD), no.339(DC) |
| ページ範囲 | pp.43-48 |
| ページ数 | 6 |
| 発行日 | 2007-11-15 (VLD, DC) |
[研究会発表申込システムのトップページに戻る]