Article contents
Algorithmic complexity of shape grammar implementation
Published online by Cambridge University Press: 09 May 2018
Abstract
Computer-based shape grammar implementations aim to support creative design exploration by automating rule-application. This paper reviews existing shape grammar implementations in terms of their algorithmic complexity, extends the definition of shape grammars with sets of transformations for rule application, categorizes (parametric and non-parametric) sets of transformations, and analyses these categories in terms of the resulting algorithmic complexity. Specifically, it describes how different sets of transformations admit different numbers of targets (i.e., potential inputs) for rule application. In the non-parametric case, this number is quadratic or cubic, while in the parametric case, it can be non-polynomial, depending on the size of the target shape. The analysis thus yields lower bounds for the algorithmic complexity of shape grammar implementations that hold independently of the employed algorithm or data structure. Based on these bounds, we propose novel matching algorithms for non-parametric and parametric shape grammar implementation and analyze their complexity. The results provide guidance for future, general-purpose shape grammar implementations for design exploration.
- Type
- Regular Articles
- Information
- AI EDAM , Volume 32 , Special Issue 2: Advances in Implemented Shape Grammars: Solutions and Applications , May 2018 , pp. 138 - 146
- Copyright
- Copyright © Cambridge University Press 2018
References
- 9
- Cited by