Small candidate set for translational pattern search

In this paper, we study the following pattern search problem: Given a pair of point sets A and B in fixed dimensional space R^d, with |B| = n, |A| = m and n ≥ m, the pattern search problem is to find the translations T 's of A such that each of the identified translations induces a matching between T (A) and a subset B⁰ of B with cost no more than some given threshold, where the cost is defined as the minimum bipartite matching cost of T (A) and B⁰. We present a novel algorithm to produce a small set of candidate translations for the pattern search problem. For any B⁰ ⊆ B with |B⁰| = |A|, there exists at least one translation T in the candidate set such that the minimum bipartite matching cost between T (A) and B⁰ is no larger than (1 + ε) times the minimum bipartite matching cost between A and B⁰ under any translation (i.e., the optimal translational matching cost). We also show that there exists an alternative solution to this problem, which constructs a candidate set of size O(n log² n) in O(n log² n) time with high probability of success. As a by-product of our construction, we obtain a weak ε-net for hypercube ranges, which significantly improves the construction time and the size of the candidate set. Our technique can be applied to a number of applications, including the translational pattern matching problem.