| id |
cf2009_757 |
| authors |
Yue, Kui; Krishnamurti, Ramesh and Grobler, François |
| year |
2009 |
| title |
Computation-friendly shape grammars: Detailed by a sub-framework 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 |
NP-hardness 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 computation-friendly parametric shape grammar interpreters is proposed, which is further detailed by a sub-framework over parametric two-dimensional rectangular shapes. As both the proof of NP-hardness and rectangular sub-framework invoke elements in graph theory, the relationship between shape and graph grammars is also explored. |
| keywords |
Parametric subshape recognition, NP-hard, graph grammar |
| series |
CAAD Futures |
| email |
|
| full text |
 file.pdf (3,699,030 bytes) |
| references |
Content-type: 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, 323-350
|
|
|
|
|
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, 295-323
|
|
|
|
|
Krishnamurti, R. (1981)
The construction of shapes
, Environment and Planning B: Planning and Design, 8, 5-40
|
|
|
|
|
McCormack, J.P. and Cagan, J. (2002)
Supporting Designer’s Hierarchies through Parametric Shape Recognition
, Environment and Planning B: Planning and Design, 29, 913-931
|
|
|
|
|
Rozenberg, G. (ed.) (1997)
Handbook of Graph Grammars and Computing by Graph Transformation, vol. I
, Foundations, World Scientific Publishing Co
|
|
|
|
|
Stiny, G. (1977)
Ice-ray: a note on Chinese Lattice Designs
, Environment and Planning B: Planning and Design, 4, 89-98
|
|
|
|
|
Stiny, G. (1980)
Introduction to Shape and Shape Grammars
, Environment and Planning B: Planning and Design, 7, 343-351
|
|
|
|
|
Stiny, G. (2006)
Shape: Talking about Seeing and Doing
, MIT Press, Cambridge
|
|
|
|
| last changed |
2009/06/08 20:53 |
|
