POINT SET PATTERN-MATCHING IN D-DIMENSIONS

In this paper we apply computational geometry techniques to obtain an efficient algorithm for the following point set pattern matching probl em. Given a set S of n points and a set P of k points in the d-dimensi onal Euclidean space, determine whether P matches any k-subset of S, w here a match can be any similarity, i.e., the set P is allowed to unde rgo translation, rotation, reflection, and global scaling. Motivated b y the need to traverse the sets in an orderly fashion to shun exponent ial complexity, we circumvent the lack of a total order for points in high-dimensional spaces by using an extension of one-dimensional sorti ng to higher dimensions (which we call ''circular sorting''). This mec hanism enables us to achieve the orderly traversal we sought. An optim al algorithm (in time and space) is described for performing circular sorting in arbitrary dimensions. The time complexity of the resulting algorithm for point set pattern matching is O(n log n + kn) for dimens ion one and O(kn(d)) for dimension d greater than or equal to 2.