1-2hit |
Hidenori OHTA Toshinori YAMADA Chikaaki KODAMA Kunihiro FUJIYOSHI
A 3D-dissection (A rectangular solid dissection) is a dissection of a rectangular solid into smaller rectangular solids by planes. In this paper, we propose an O-sequence, a string of representing any 3D-dissection which is dissected by only non-crossing rectangular planes. We also present a necessary and sufficient condition for a given string to be an O-sequence.
Chikaaki KODAMA Kunihiro FUJIYOSHI
This paper discusses how to minimize the number of dissection lines regarded as wiring channels on a floorplan corresponding to a placement of n modules. In a floorplan (rectangular dissection), the number of dissection lines exceeds the number of rooms exactly by three. Since a floorplan obtained from a given module placement may have many empty rooms where no module is assigned, redundant wiring channels and wire bends may also be generated. Hence, in order to reduce redundant channels and wire bends, removal of empty rooms is required. For this purpose, we formulate a problem of obtaining a floorplan with the minimum possible empty rooms based on a given module placement. Then, we propose a method of removing as many redundant empty rooms as possible by merging dissection lines on a floorplan in O(n) time. The number of empty rooms in the resultant floorplan is reduced to n- or less.