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.