Please use this identifier to cite or link to this item: https://doi.org/10.1017/S0890060417000440
Title: Algorithmic complexity of shape grammar implementation
Authors: Wortmann, Thomas
Stouffs, Rudi 
Keywords: Science & Technology
Technology
Computer Science, Artificial Intelligence
Computer Science, Interdisciplinary Applications
Engineering, Multidisciplinary
Engineering, Manufacturing
Computer Science
Engineering
Shape grammars
shape grammar implementations
algorithmic complexity
tractability
COLOR GRAMMARS
CONTINUITY
Issue Date: 1-May-2018
Publisher: CAMBRIDGE UNIV PRESS
Citation: Wortmann, Thomas, Stouffs, Rudi (2018-05-01). Algorithmic complexity of shape grammar implementation. AI EDAM-ARTIFICIAL INTELLIGENCE FOR ENGINEERING DESIGN ANALYSIS AND MANUFACTURING 32 (2) : 138-146. ScholarBank@NUS Repository. https://doi.org/10.1017/S0890060417000440
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.
Source Title: AI EDAM-ARTIFICIAL INTELLIGENCE FOR ENGINEERING DESIGN ANALYSIS AND MANUFACTURING
URI: https://scholarbank.nus.edu.sg/handle/10635/194368
ISSN: 0890-0604,1469-1760
DOI: 10.1017/S0890060417000440
Appears in Collections:Staff Publications
Elements

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
algorithmic_complexity_of_shape_grammar_implementation.pdf289.06 kBAdobe PDF

OPEN

PublishedView/Download

SCOPUSTM   
Citations

5
checked on Dec 4, 2021

WEB OF SCIENCETM
Citations

5
checked on Sep 23, 2021

Page view(s)

84
checked on Dec 2, 2021

Download(s)

2
checked on Dec 2, 2021

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.