id 
cf2009_757 
authors 
Yue, Kui; Krishnamurti, Ramesh and Grobler, François 
year 
2009 
title 
Computationfriendly shape grammars: Detailed by a subframework over parametric 2D rectangular shapes 
source 
T. Tidafi and T. Dorta (eds) Joining Languages, Cultures and Visions: CAADFutures 2009, PUM, 2009, pp. 757 770 
summary 
NPhardness of parametric subshape recognition for an arbitrary number of open terms is proven. Guided by this understanding of the complexity of subshape recognition, a framework for computationfriendly parametric shape grammar interpreters is proposed, which is further detailed by a subframework over parametric twodimensional rectangular shapes. As both the proof of NPhardness and rectangular subframework invoke elements in graph theory, the relationship between shape and graph grammars is also explored. 
keywords 
Parametric subshape recognition, NPhard, graph grammar 
series 
CAAD Futures 
email 
kyue@andrew.cmu.edu 
full text 
file.pdf (3,699,030 bytes) 
references 
Contenttype: text/plain

Brouno, C. (1990)
Graph Rewriting: An Algebraic and Logic Approach
, Handbook of Theoretical Computer Science, vol. B: Formal Models and Semantics, MIT Press




Chau, H.H., Chen, X., McKay, A. and Pennington, A. (2004)
Evaluation of a 3D Shape Grammar Implementation
, J.S. Gero (ed.), Design Computing and Cognition ‘04. Boston




Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2004)
Introduction to Algorithms, Second Edition
, The MIT Press




Drewes, F. and Kreowski, H.J. (1999)
Picture Generation by Collage Grammars
, Handbook of Graph Grammars and Computing by Graph Transformation, vol. 2, Applications, Languages, and Tools, World Scientific Publishing Co




Flemming, U. (1987)
More than the Sum of Parts: the Grammar of Queen Anne Houses
, Environment and Planning B: Planning and Design, 14, 323350




Koning, H. and Eizenberg, J. (1981)
The Language of the Prairie: Frank Lloyd Wright’s Prairie houses
, Environment and Planning B: Planning and Design, 8, 295323




Krishnamurti, R. (1981)
The construction of shapes
, Environment and Planning B: Planning and Design, 8, 540




McCormack, J.P. and Cagan, J. (2002)
Supporting Designer’s Hierarchies through Parametric Shape Recognition
, Environment and Planning B: Planning and Design, 29, 913931




Rozenberg, G. (ed.) (1997)
Handbook of Graph Grammars and Computing by Graph Transformation, vol. I
, Foundations, World Scientific Publishing Co




Stiny, G. (1977)
Iceray: a note on Chinese Lattice Designs
, Environment and Planning B: Planning and Design, 4, 8998




Stiny, G. (1980)
Introduction to Shape and Shape Grammars
, Environment and Planning B: Planning and Design, 7, 343351




Stiny, G. (2006)
Shape: Talking about Seeing and Doing
, MIT Press, Cambridge




last changed 
2009/06/08 18:53 
