Geometric Pattern Matching Reduces to k -SUM

Boris Aronov; Jean Cardinal

doi:10.1007/s00454-021-00324-1

Geometric Pattern Matching Reduces to k -SUM

Boris Aronov, Jean Cardinal

Research output: Contribution to journal › Article › peer-review

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≥ 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.

Original language	English (US)
Pages (from-to)	850-859
Number of pages	10
Journal	Discrete and Computational Geometry
Volume	68
Issue number	3
DOIs	https://doi.org/10.1007/s00454-021-00324-1
State	Published - Oct 2022

Keywords

3-SUM
Geometric pattern matching
k-SUM

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/s00454-021-00324-1

Cite this

@article{4253aa449ff94c52b2bf63615bf998f5,

title = "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≥ 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.",

keywords = "3-SUM, Geometric pattern matching, k-SUM",

author = "Boris Aronov and Jean Cardinal",

note = "Publisher Copyright: {\textcopyright} 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2022",

month = oct,

doi = "10.1007/s00454-021-00324-1",

language = "English (US)",

volume = "68",

pages = "850--859",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - Geometric Pattern Matching Reduces to k -SUM

AU - Aronov, Boris

AU - Cardinal, Jean

PY - 2022/10

Y1 - 2022/10

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 - 3-SUM

KW - Geometric pattern matching

KW - k-SUM

UR - http://www.scopus.com/inward/record.url?scp=85115810118&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85115810118&partnerID=8YFLogxK

U2 - 10.1007/s00454-021-00324-1

DO - 10.1007/s00454-021-00324-1

M3 - Article

AN - SCOPUS:85115810118

SN - 0179-5376

VL - 68

SP - 850

EP - 859

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 3

ER -

Geometric Pattern Matching Reduces to k -SUM

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this