#
A Geometric Approach to Fingerprint Matching: Oriented Point-Set Pattern Matching

##
Jordan Jorgensen

Motivated by the problem of fingerprint matching, we present geometric approximation algorithms for matching a pattern point set against a background point set, where the points have angular orientations in addition to their positions. We define such matching problems in terms of minimizing a directed Hausdorff distance between a pair of such oriented point sets, based on an underlying metric that combines positional distance and angular distance. We present a family of fast approximation algorithms for such oriented point-set pattern matching problems that are based on simple pin-and-query and grid-refinement strategies. Our algorithms achieve an approximation ratio of 1 + ε, for any fixed constant ε > 0.