TY - GEN
T1 - Geometric pattern matching reduces to k-SUM
AU - Aronov, Boris
AU - Cardinal, Jean
N1 - Funding Information:
Partially supported by NSF grant CCF-15-40656 and by grant 2014/170 from the US-Israel Binational Science Foundation. Work by B.A. on this paper has been partially carried out while visiting ULB in November-December 2019, with support from ULB and F.R.S.FNRS (Fonds National de la Recherche Scientifique). Jean Cardinal: Supported by the F.R.S.-FNRS (Fonds National de la Recherche Scientifique) under CDR Grant J.0146.18.
Publisher Copyright:
© Boris Aronov and Jean Cardinal.
PY - 2020/12
Y1 - 2020/12
N2 - We prove that some exact geometric pattern matching problems reduce in linear time to k-SUM when the pattern has a fixed size k. This holds in the real RAM model for searching for a similar copy of a set of k ≥ 3 points within a set of n points in the plane, and for searching for an affine image of a set of k ≥ d + 2 points within a set of n points in d-space. As corollaries, we obtain improved real RAM algorithms and decision trees for the two problems. In particular, they can be solved by algebraic decision trees of near-linear height.
AB - We prove that some exact geometric pattern matching problems reduce in linear time to k-SUM when the pattern has a fixed size k. This holds in the real RAM model for searching for a similar copy of a set of k ≥ 3 points within a set of n points in the plane, and for searching for an affine image of a set of k ≥ d + 2 points within a set of n points in d-space. As corollaries, we obtain improved real RAM algorithms and decision trees for the two problems. In particular, they can be solved by algebraic decision trees of near-linear height.
KW - Geometric pattern matching
KW - K-SUM problem
KW - Linear decision trees
UR - http://www.scopus.com/inward/record.url?scp=85100928733&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85100928733&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2020.32
DO - 10.4230/LIPIcs.ISAAC.2020.32
M3 - Conference contribution
AN - SCOPUS:85100928733
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 321
EP - 329
BT - 31st International Symposium on Algorithms and Computation, ISAAC 2020
A2 - Cao, Yixin
A2 - Cheng, Siu-Wing
A2 - Li, Minming
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 31st International Symposium on Algorithms and Computation, ISAAC 2020
Y2 - 14 December 2020 through 18 December 2020
ER -