2026-08-17T23:48:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13376 2024-03-06T10:51:49Z ddc:004 open_access

Geometric Pattern Matching Reduces to k-SUM Aronov, Boris Cardinal, Jean Geometric pattern matching k-SUM problem Linear decision trees We prove that some exact geometric pattern matching problems reduce in linear time to o 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Boris Aronov and Jean Cardinal 2020 Is Part Of LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2020.32 urn:nbn:de:0030-drops-133760 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.32 eng https://creativecommons.org/licenses/by/3.0/legalcode