K-dimensional trees, abbreviated as k-d trees in the following, are binary search and partitioning trees that represent a set of n points in a multi-dimensional space. K-d tree data structures have primarily been used for nearest neighbor queries and several other query types, for example in database applications. In the context of a research project by Katja Knecht at the Bauhaus-University Weimar concerned with the development of a creative evolutionary design method for layout problems in architecture and urban design, spatial partitioning with k-d trees has been applied as a partial solution to generate floor plan layouts. Unlike, for example, packing algorithms and slicing tree structures, the employment of k-d tree algorithms in combination with evolutionary algorithms to generate floor plan layouts has not previously been examined in the scope presented here.

In the application developed in this project the k-d tree algorithm is initially used to subdivide a given rectangular area. The dividing lines thereby correspond to eventual spatial boundaries. By combining the k-d tree algorithm with genetic algorithms and evolutionary strategies, layouts can – in the current version – be optimized in three criteria dimensions (size, ratio and topology). Through user interaction the layouts can be dynamically adjusted and altered in real time. The result is a generative mechanism that provides an interesting and promising alternative to existing well- established algorithms for the creative and evolutionary solution of layout problems in architecture and urban design.