| 講演名 | 2001/11/22 O-Treeを拡張した、レクトリニア多角形パッキング手法 藤吉 邦洋, 岡本 悟, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 矩形パッキングの表現方法として提案されたO-treeは、どんな左下詰めパッキングでも表現でき、与えられたO-Treeに基づいたパッキングを矩形数nに対してO(n)時間で求めることができるという特長をもっている。近年、O-treを拡張し、その特長を保ったままL型多角形のパッキングを表現する手法が提案されたが、L型より複雑な多角形には対応できてなかった。本稿では、O-Treeの特長をできるだけ保ったままレクトリニア多角形パッキングの表現に拡張する方法を提案する。そして、与えられたO-Treeに基づいた左下詰めパッキングを、多角形数をmとしてO(nm)時間にて、多角形が凸型だけの場合にはO(n)時間で求めることができる手法を提案する。 |
| 抄録(英) | O-tree, which has been proposed to represent rectangle packing, has some outstanding properties. One of them is that the packing which keeps all the constraints imposed by a given O-tree can be obtained in O(n)time, where n is the number of rectangles. Recently, methods to extend O-tree to represent L-shaped block packing were proposed. In this paper, a method to extend O-tree to represent rectilinear block packing is proposed. Also, a novel algorithm to obtain the packing which keeps all the constraints imposed by any feasible O-tree in O(nm)time is proposed, where m is the number of rectilinear blocks.The proposed algorithm can obtain the packing in O(n)time if all the blocks are convex. |
| キーワード(和) | O-tree / パッキング / レクトリニア多角形 / 凸多角形 / 凹多角形 |
| キーワード(英) | O-tree / packing / rectilinear-block / convex-block / concave-block |
| 資料番号 | VLD2001-104,ICD2001-149,FTS2001-51 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2001/11/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | O-Treeを拡張した、レクトリニア多角形パッキング手法 |
| サブタイトル（和） | |
| タイトル（英） | Rectilinear Block Packing using an O-Tree Representation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | O-tree / O-tree |
| キーワード(2)（和/英） | パッキング / packing |
| キーワード(3)（和/英） | レクトリニア多角形 / rectilinear-block |
| キーワード(4)（和/英） | 凸多角形 / convex-block |
| キーワード(5)（和/英） | 凹多角形 / concave-block |
| 第 1 著者 氏名（和/英） | 藤吉 邦洋 / Kunihiro FUZIYOSHI |
| 第 1 著者 所属（和/英） | 東京農工大学工学部電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 第 2 著者 氏名（和/英） | 岡本 悟 / Satoru OKAMOTO |
| 第 2 著者 所属（和/英） | 東京農工大学工学部電気電子工学科 Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| 発表年月日 | 2001/11/22 |
| 資料番号 | VLD2001-104,ICD2001-149,FTS2001-51 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 467 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |