Geometric Pattern Matching Reduces to k -SUM
Geometric Pattern Matching Reduces to k -SUM
复制标题
几何图案匹配简化为 k -SUM
DOI：
10.1007/s00454-021-00324-1
复制
发表时间：
2021
影响因子：
0.8
通讯作者：
Cardinal, Jean
中科院分区：
文献类型：
--
作者：
Aronov, Boris;Cardinal, Jean
我们证明，当图案具有固定大小 k 时，一些精确的几何图案匹配问题会减少线性时间 tok-SUM 。这在真实 RAM 模型中适用，用于在平面中的一组 n 点内搜索一组点的相似副本，以及在一组 n 点 ind-space 内搜索一组点的仿射图像。作为推论，我们获得了针对这两个问题的改进的真实 RAM 算法和决策树。特别是，它们可以通过近线性高度的代数决策树来求解。
We prove that some exact geometric pattern matching problems reduce in linear time tok-SUMwhen the pattern has a fixed sizek. This holds in the real RAM model for searching for a similar copy of a set ofpoints within a set ofnpoints in the plane, and for searching for an affine image of a set ofpoints within a set ofnpoints ind-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.