@techreport{TR-DCC-92-02,
  number = {DCC-92-02},
  author = {de Rezende, Pedro J. and Lee, Der-Tsai},
  title = {Point Set Pattern Matching in $d$-Dimensions},
  month = {July},
  year = {1992}, 
  institution = {Department of Computer Science, University of Campinas},
  note = {In English, 29 pages.
    \par\selectlanguage{english}\textbf{Abstract}
      In this paper, we apply computational geometry techniques to
      obtain an efficient algorithm for the following point set
      pattern matching problem.  Given a set $S$ of $n$ points and a
      set $P$ of $k$ points in the $d$-dimensional Euclidean space,
      determine whether $P$ matches any $k$-subset of $S$, where a
      match can be any similarity, i.e., the set $P$ is allowed to
      undergo translation, rotation, reflection and global scaling.
      Motivated by the need to traverse the sets in an orderly fashion
      to shun exponential complexity, we circumvent the lack of a
      total order for points in high dimensional spaces by presenting
      an extension of one-dimensional sorting to higher dimensions
      (called circular sorting).  This mechanism, which is of interest
      in its own right, enables us to achieve the orderly traversal we
      sought. An optimal 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 dimension one and $O(kn^d)$ for
      dimension $d\geq 2$.
  }
}