论文标题
几何图案匹配可减少到k-sum
Geometric Pattern Matching Reduces to k-SUM
论文作者
论文摘要
我们证明，当模式具有固定尺寸$ k $时，线性时间的一些确切的几何图案匹配问题将线性时间降低至$ k $ -sum。这是在真正的RAM型号中搜索一组$ k \ geq 3 $点的类似副本，在飞机上的$ n $点内，并在$ d $ space中的一组$ n $点中搜索一组$ k \ geq d+2 $点的仿射图像。 作为推论，我们为这两个问题获得了改进的实际RAM算法和决策树。特别是，可以通过近线性高度的代数决策树来解决它们。
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\geq 3$ points within a set of $n$ points in the plane, and for searching for an affine image of a set of $k\geq 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.
