Abstract: MATH/CHEM/COMP 2002, Dubrovnik,
June 2429, 2002

Pattern matching of
colored point set in 3D
Marko Boben^{1}, Alen OrbaniC^{1}, Tomaz Pisanski^{1}, and Ante Graovac^{2} ^{1}IMFM,
University of Ljubljana, Jadranska 19, SI1000 Ljubljan, Slovenia ^{2} Rudjer Boskovic Institute, POB 180, HR10002 Zagreb, Croatia The following problems are considered here: Problem 1. Given a large collection of points
S in 3D space and a small pattern set P find all occurrences of a subset P’
in S such that P’ is obtained from P as a result of rotation, translation and
scaling. Problem 2. Same as Problem 1, except that points
in both sets are labeled (colored). Efficient algorithms for both
problems are presented and applications to chemical and biochemical
situations are discussed. Both problems could be diversified into a series of
problems by modifying the set of allowed transformations like dropping the
scaling transformation or introducing the mirror transformations. The algorithms developed here
should find applications in correcting the approximate geometries of
fullerenes and other cages to achieve presumed symmetry. 