Abstract: Consider a set of points in two dimensional Euclidean space for which each point is associated with an orientation. Such sets of points are common in areas such as fingerprint matching where fingerprints are characterized by their minutia, which are points that have both a location and a direction. We present a metric for defining the distance between two sets of these points and we describe a ($1+\epsilon$)-approximation algorithm for solving the approximate point set pattern matching problem using our metric.
Joint work with David Eppstein, and Michael T. Goodrich, and Manuel Torres