## Oct 7, 2016:

#
Improved Approximation Bounds for Planar Point Pattern Matching

## Authors: Minkyoung Cho and David M. Mount

## Speaker: Jordan Jorgensen

Abstract: We analyze the performance of simple algorithms for matching two planar
point sets under rigid transformations so as to minimize the directed Hausdorff distance
between the sets. This is a well studied problem in computational geometry. Goodrich,
Mitchell, and Orletsky presented a very simple approximation algorithm for this problem,
which computes transformations based on aligning pairs of points. They showed that
their algorithm achieves an approximation ratio of 4. We introduce a modification to their
algorithm, which is based on aligning midpoints rather than endpoints. This modification
has the same simplicity and running time as theirs, and we show that it achieves a better
approximation ratio of roughly 3.14. We also analyze the approximation ratio in terms of
a instance-specific parameter that is based on the ratio between diameter of the pattern
set to the optimum Hausdorff distance. We show that as this ratio increases (as is
common in practical applications) the approximation ratio approaches 3 in the limit. We
also investigate the performance of the algorithm by Goodrich et al. as a function of this
ratio, and present nearly matching lower bounds on the approximation ratios of both
algorithms.