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



Pattern matching of colored point set in 3D


Marko Boben1, Alen OrbaniC1, Tomaz Pisanski1, and Ante Graovac2


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


2 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.