Wall representations of rectangular dissections and their use in automated space allocation

A procedure is described which generates dissections of rectangles into rectangular components in order to obtain solutions to space-allocation problems which are restricted through topological and dimensional constraints. Solutions are generated in two steps: step 1 determines basic geometric properties of the arrangements to be produced, and step 2 computes the dimensions of the spaces in such an arrangement. Both steps are based on 'wall representations' of the solutions. These representations allow geometric relations and operations to be transformed into relations and operations defined on character strings. They furthermore allow the (possibly infinite) set of solutions to be systematically searched for a finite set of 'principal options'. The importance of linear-programming techniques for step 2 is described.