Back to Search
Start Over
Small Candidate Set for Translational Pattern Search.
- Source :
-
Algorithmica . Oct2022, Vol. 84 Issue 10, p3034-3053. 20p. - Publication Year :
- 2022
-
Abstract
- 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 d , ϵ (n log 2 n) in O d , ϵ (n log 2 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *BIPARTITE graphs
*HYPERCUBES
*COST
*PROBABILITY theory
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 84
- Issue :
- 10
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 159441270
- Full Text :
- https://doi.org/10.1007/s00453-022-00997-x