CS 269S, Fall 2017: Theory Seminar
Bren Hall, Room 1300, 1pm
November 17, 2017:

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.