On the complexity of the partial least-squares matching Voronoi diagram

Abstract

Given two point sets of sizes n and m, we study the partial matching problem of translating the smaller point set to a position where it is best resembled by an equally sized subset of the larger point set. Mea-suring the similarity is done by the sum of squares of the Euclidean distances between the matched points in either set. A Voronoi-type diagram can be associ-ated in a natural way. We prove that the complexity of this diagram is O(m!mdn2d), where n is the size of the bigger set. A combinatorial problem on stable matchings that arises from our argument is of inde-pendent interest. 1