For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Air-Pressure Model and Fast Algorithms for Zero-Wasted-Area Layout of General Floorplan
Tomonori IZUMI Atsushi TAKAHASHI Yoji KAJITANI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1998/05/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
floorplan, layout, area optimization, air-pressure, zero-wasted-area,
Full Text: PDF>>
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.