CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

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 kyue@andrew.cmu.edu
full text file.pdf (3,699,030 bytes)
references Content-type: text/plain
details citation check to select
100%; open Brouno, C. (1990) Find in CUMINCAD Graph Rewriting: An Algebraic and Logic Approach , Handbook of Theoretical Computer Science, vol. B: Formal Models and Semantics, MIT Press
100%; open Chau, H.H., Chen, X., McKay, A. and Pennington, A. (2004) Find in CUMINCAD Evaluation of a 3D Shape Grammar Implementation , J.S. Gero (ed.), Design Computing and Cognition ‘04. Boston
100%; open Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C. (2004) Find in CUMINCAD Introduction to Algorithms, Second Edition , The MIT Press
100%; open Drewes, F. and Kreowski, H.J. (1999) Find in CUMINCAD Picture Generation by Collage Grammars , Handbook of Graph Grammars and Computing by Graph Transformation, vol. 2, Applications, Languages, and Tools, World Scientific Publishing Co
100%; open Flemming, U. (1987) Find in CUMINCAD More than the Sum of Parts: the Grammar of Queen Anne Houses , Environment and Planning B: Planning and Design, 14, 323-350
100%; open Koning, H. and Eizenberg, J. (1981) Find in CUMINCAD The Language of the Prairie: Frank Lloyd Wright’s Prairie houses , Environment and Planning B: Planning and Design, 8, 295-323
100%; open Krishnamurti, R. (1981) Find in CUMINCAD The construction of shapes , Environment and Planning B: Planning and Design, 8, 5-40
100%; open McCormack, J.P. and Cagan, J. (2002) Find in CUMINCAD Supporting Designer’s Hierarchies through Parametric Shape Recognition , Environment and Planning B: Planning and Design, 29, 913-931
100%; open Rozenberg, G. (ed.) (1997) Find in CUMINCAD Handbook of Graph Grammars and Computing by Graph Transformation, vol. I , Foundations, World Scientific Publishing Co
100%; open Stiny, G. (1977) Find in CUMINCAD Ice-ray: a note on Chinese Lattice Designs , Environment and Planning B: Planning and Design, 4, 89-98
100%; open Stiny, G. (1980) Find in CUMINCAD Introduction to Shape and Shape Grammars , Environment and Planning B: Planning and Design, 7, 343-351
100%; open Stiny, G. (2006) Find in CUMINCAD Shape: Talking about Seeing and Doing , MIT Press, Cambridge

last changed 2009/06/08 18:53
HOMELOGIN (you are user _anon_331219 from group guest) Works Powered by SciX Open Publishing Services 1.002