Premium
Cell‐shedding transformations, equivalence relations, and similarity measures for square‐cell configurations
Author(s) -
Harary Frank,
Mezey Paul G.
Publication year - 1997
Publication title -
international journal of quantum chemistry
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.484
H-Index - 105
eISSN - 1097-461X
pISSN - 0020-7608
DOI - 10.1002/(sici)1097-461x(1997)62:4<353::aid-qua3>3.0.co;2-v
Subject(s) - equivalence (formal languages) , equivalence relation , similarity (geometry) , mathematics , square (algebra) , algorithm , computer science , discrete mathematics , artificial intelligence , geometry , image (mathematics)
A family of related techniques for the reduction of square‐cell configurations (“animals”) to simpler ones by cell‐shedding processes provide physically motivated, novel approaches for shape characterization and similarity criteria as well as similarity measures based on equivalence relations. The two main algorithms, cs k , k = 1, 2, involve the simultaneous “shedding” of all cells having precisely k sides exposed on the periphery of the animal; the shedding steps are repeated as long as the resulting structure is an animal. Since the termination criteria of these two algorithms are different, they can be combined sequentially into composite algorithms, leading to various alternative shape characterizations and equivalence relations. The third main algorithm, cs 32 , involves incomplete elimination of peripheral cells of a given type, thus retaining some additional local shape features inherited from the original animal. Following the introduction of these transformations, some of their properties are derived and several examples are discussed. © 1997 John Wiley & Sons, Inc. Int J Quant Chem 62 : 353–361, 1997