IEICE TRANSACTIONS on Fundamentals
Air-Pressure Model and Fast Algorithms for Zero-Wasted-Area Layout of General Floorplan
Summary :
A floorplan is a partition of a rectangle into subrectangles, each of which is associated with a module. Zero-wasted-area layouts are known to exist when the height and width of modules are constrained only by the area, and several methods have been proposed for deriving such layouts. However, because these methods are global and indirect, they are inherently slow. We propose a new algorithm which simulates the air-pressure mechanics. It begins with a layout, which is not necessarily feasible, and iterates the movement of one wall at a time to the force-balancing position. The key issue is that it is guaranteed that every movement makes a current layout approach a zero-wasted-area layout by the measure of energy which is defined here. Experimental results on the example in several literatures and artificially made complex examples showed very fast convergence. The algorithm is evolved to methods which move all the walls simultaneously, resulting in a further speed enhancement.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E81-A No.5 pp.857-865
- Publication Date
- 1998/05/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tomonori IZUMI, Atsushi TAKAHASHI, Yoji KAJITANI, "Air-Pressure Model and Fast Algorithms for Zero-Wasted-Area Layout of General Floorplan" in IEICE TRANSACTIONS on Fundamentals,
vol. E81-A, no. 5, pp. 857-865, May 1998, doi: .
Abstract: A floorplan is a partition of a rectangle into subrectangles, each of which is associated with a module. Zero-wasted-area layouts are known to exist when the height and width of modules are constrained only by the area, and several methods have been proposed for deriving such layouts. However, because these methods are global and indirect, they are inherently slow. We propose a new algorithm which simulates the air-pressure mechanics. It begins with a layout, which is not necessarily feasible, and iterates the movement of one wall at a time to the force-balancing position. The key issue is that it is guaranteed that every movement makes a current layout approach a zero-wasted-area layout by the measure of energy which is defined here. Experimental results on the example in several literatures and artificially made complex examples showed very fast convergence. The algorithm is evolved to methods which move all the walls simultaneously, resulting in a further speed enhancement.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e81-a_5_857/_p
Copy
@ARTICLE{e81-a_5_857,
author={Tomonori IZUMI, Atsushi TAKAHASHI, Yoji KAJITANI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Air-Pressure Model and Fast Algorithms for Zero-Wasted-Area Layout of General Floorplan},
year={1998},
volume={E81-A},
number={5},
pages={857-865},
abstract={A floorplan is a partition of a rectangle into subrectangles, each of which is associated with a module. Zero-wasted-area layouts are known to exist when the height and width of modules are constrained only by the area, and several methods have been proposed for deriving such layouts. However, because these methods are global and indirect, they are inherently slow. We propose a new algorithm which simulates the air-pressure mechanics. It begins with a layout, which is not necessarily feasible, and iterates the movement of one wall at a time to the force-balancing position. The key issue is that it is guaranteed that every movement makes a current layout approach a zero-wasted-area layout by the measure of energy which is defined here. Experimental results on the example in several literatures and artificially made complex examples showed very fast convergence. The algorithm is evolved to methods which move all the walls simultaneously, resulting in a further speed enhancement.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Air-Pressure Model and Fast Algorithms for Zero-Wasted-Area Layout of General Floorplan
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 857
EP - 865
AU - Tomonori IZUMI
AU - Atsushi TAKAHASHI
AU - Yoji KAJITANI
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E81-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 1998
AB - A floorplan is a partition of a rectangle into subrectangles, each of which is associated with a module. Zero-wasted-area layouts are known to exist when the height and width of modules are constrained only by the area, and several methods have been proposed for deriving such layouts. However, because these methods are global and indirect, they are inherently slow. We propose a new algorithm which simulates the air-pressure mechanics. It begins with a layout, which is not necessarily feasible, and iterates the movement of one wall at a time to the force-balancing position. The key issue is that it is guaranteed that every movement makes a current layout approach a zero-wasted-area layout by the measure of energy which is defined here. Experimental results on the example in several literatures and artificially made complex examples showed very fast convergence. The algorithm is evolved to methods which move all the walls simultaneously, resulting in a further speed enhancement.
ER -
English
