Abstract: MATH/CHEM/COMP 2002, Dubrovnik, June 24-29, 2002

Pattern matching of colored point set in 3D

Marko Boben¹, Alen OrbaniC¹, Tomaz Pisanski¹, and Ante Graovac²

¹IMFM, University of Ljubljana, Jadranska 19, SI-1000 Ljubljan, Slovenia

² Rudjer Boskovic Institute, POB 180, HR-10002 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.