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
details 
citation 
check to select 

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 
