配置の数理：多数の長方形を最小面積に埋め込む

• Item type: SIG Technical Reports(1)
• 公開日: 1998-09-21
• タイトル: 配置の数理：多数の長方形を最小面積に埋め込む
• タイトル / 言語: en
• タイトル: On Packing of Rectangles into a Small Plane Area
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京工業大学 工学部 電気・電子工学科
• 著者所属(英): en
• 著者所属(英): Dept. of Electrical and Electronic Engrg., Tokyo Institute of Technology
• 著者名: 梶谷, 洋司
• 著者名(英): Yoji, Kajitani
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 多数の長方形を平面上に効率良く配置する問題が難しい理由を解析し，新しい技術の必然性を抽象し，それに応える一意四方位方式と呼ぶ方法を二通り紹介する．それぞれBSGおよびSequence-Pairと呼ばれるデータ構造に基づく．実装実験によれば数万個でも十分な品質で配置できるようになり，実用上限界は無くなったと言える．一般矩形，配線面積考慮，ソフト図形の配置，あるいは既配置図形，変形パッケージの扱い，更には3次元配置への発展，などの研究状況を紹介する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We discuss about possible reasons why the problem to pack rectangles on a plane into a small area is hard. Based on the conclusion, two new ideas, BSG and Sequence-Pair, are introduced which are special data structures, called the quad-direction-methods. Experiments show that they easily pack hundreds of rectangles by flat computation, even tens of thousands rectangles if the method implemented hierachically. It is a breakthrough for the practical problem size. Several enhancements and developments are introduced. Examples are, packing of objects which are of general shape, routing area included, soft area constrained, positional constrained, and packing into an irregular area, and packing of cubes into a 3-dimensional shape.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 情報処理学会研究報告システムLSI設計技術（SLDM）; 巻 1998, 号 87(1998-SLDM-089), p. 7-14, 発行日 1998-09-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会