Geometric pattern matching reduces to k-SUM

Boris Aronov, Jean Cardinal

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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 languageEnglish (US)
    Title of host publication31st International Symposium on Algorithms and Computation, ISAAC 2020
    EditorsYixin Cao, Siu-Wing Cheng, Minming Li
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    Pages321-329
    Number of pages9
    ISBN (Electronic)9783959771733
    DOIs
    StatePublished - Dec 2020
    Event31st International Symposium on Algorithms and Computation, ISAAC 2020 - Virtual, Hong Kong, China
    Duration: Dec 14 2020Dec 18 2020

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    Volume181
    ISSN (Print)1868-8969

    Conference

    Conference31st International Symposium on Algorithms and Computation, ISAAC 2020
    CountryChina
    CityVirtual, Hong Kong
    Period12/14/2012/18/20

    Keywords

    • Geometric pattern matching
    • K-SUM problem
    • Linear decision trees

    ASJC Scopus subject areas

    • Software

    Fingerprint Dive into the research topics of 'Geometric pattern matching reduces to k-SUM'. Together they form a unique fingerprint.

    Cite this