We study local similarity based distance measures for point-patterns. Such measures can be used for matching point-patterns under non-uniform transformations — a problem that naturally arises in image comparison problems. A general framework for the matching problem is introduced. We show that some of the most obvious instances of this framework lead to NP-hard optimization problems and are not approximable within any constant factor. We also give a relaxation of the framework that is solvable in polynomial time and works well in practice in our experiments with two-dimensional protein electrophoresis gel images.