2026-07-24T18:14:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11522 2024-03-06T10:48:13Z ddc:004 open_access

Small Candidate Set for Translational Pattern Search Huang, Ziyun Feng, Qilong Wang, Jianxin Xu, Jinhui Bipartite matching Alignment Discretization Approximate algorithm 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' subseteq 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+epsilon) 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^2 n) in O(n log^2 n) time with high probability of success. As a by-product of our construction, we obtain a weak epsilon-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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ziyun Huang and Qilong Feng and Jianxin Wang and Jinhui Xu 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.26 urn:nbn:de:0030-drops-115222 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.26 eng https://creativecommons.org/licenses/by/3.0/legalcode