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.