| Presentation | 2000/3/3 Area Optimization of Packing Represented by Sequence-Pair Tomokazu OHMURA, Kunihiro FUJIYOSHI, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In the rectangle packing problem, "area optimization problem", which is to minimize the whole area by rotating rectangles for 90 degrees, is proved to be NP-hard in general. But it can be solved in O (n^2) time if the packing is restricted to the slicing structure. In this paper, we propose a method using local slicing structure to solve the problem efficiently. The packing is supposed to be represented by sequence-pair, and the necessary and sufficient condition for the maximum local slicing structure is presented and proved. It is shown that the combination of the rotations can be reduced drastically by using the proposed method. The experimental results show the effectiveness of the proposed method. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | sequence-pair / slicing structure / area optimization / rectangle rotation / packing |
| Paper # | VLD99-119,ICD99-276 |
| Date of Issue |
| Conference Information | |
| Committee | ICD |
|---|---|
| Conference Date | 2000/3/3(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Integrated Circuits and Devices (ICD) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Area Optimization of Packing Represented by Sequence-Pair |
| Sub Title (in English) | |
| Keyword(1) | sequence-pair |
| Keyword(2) | slicing structure |
| Keyword(3) | area optimization |
| Keyword(4) | rectangle rotation |
| Keyword(5) | packing |
| 1st Author's Name | Tomokazu OHMURA |
| 1st Author's Affiliation | Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology() |
| 2nd Author's Name | Kunihiro FUJIYOSHI |
| 2nd Author's Affiliation | Department of Electrical and Electronic Engineering, Tokyo University of Agriculture & Technology |
| Date | 2000/3/3 |
| Paper # | VLD99-119,ICD99-276 |
| Volume (vol) | vol.99 |
| Number (no) | 661 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |