ICS Theory Group

Spring 2017: Theory Seminar
Bren Hall, Room 1423, 1:00pm


May 12, 2017:

A ($1+\epsilon$)-approximation algorithm for planar point pattern matching with orientation

Jordan Jorgensen

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