Geometric Pattern Matching Reduces to k-SUM

Abstract

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\ge 3$ points within a set of $n$ points in the plane, and for searching for an affine image of a set of $k\ge 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.