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   Vol.E81-A   No.5   pp.857-865
Publication Date: 1998/05/25
Online ISSN: 
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>>
Buy this Article

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.