Testing polynomials for vanishing on cartesian products of planar point sets

Boris Aronov, Esther Ezra, Micha Sharir

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

    Abstract

    We present subquadratic algorithms, in the algebraic decision-tree model of computation, for detecting whether there exists a triple of points, belonging to three respective sets A, B, and C of points in the plane, that satisfy a certain polynomial equation or two equations. The best known instance of such a problem is testing for the existence of a collinear triple of points in A × B × C, a classical 3SUM-hard problem that has so far defied any attempt to obtain a subquadratic solution, whether in the (uniform) real RAM model, or in the algebraic decision-tree model. While we are still unable to solve this problem, in full generality, in subquadratic time, we obtain such a solution, in the algebraic decision-tree model, that uses only roughly O(n28/15) constant-degree polynomial sign tests, for the special case where two of the sets lie on one-dimensional curves and the third is placed arbitrarily in the plane. Our technique is fairly general, and applies to any other problem where we seek a triple that satisfies a single polynomial equation, e.g., determining whether A × B × C contains a triple spanning a unit-area triangle. This result extends recent work by Barba et al. [4] and by Chan [7], where all three sets A, B, and C are assumed to be one-dimensional. While there are common features in the high-level approaches, here and in [4], the actual analysis in this work becomes more involved and requires new methods and techniques, involving polynomial partitions and other related tools. As a second application of our technique, we again have three n-point sets A, B, and C in the plane, and we want to determine whether there exists a triple (a, b, c) ∈ A×B×C that simultaneously satisfies two real polynomial equations. For example, this is the setup when testing for the existence of pairs of similar triangles spanned by the input points, in various contexts discussed later in the paper. We show that problems of this kind can be solved with roughly O(n24/13) constant-degree polynomial sign tests. These problems can be extended to higher dimensions in various ways, and we present subquadratic solutions to some of these extensions, in the algebraic decision-tree model.

    Original languageEnglish (US)
    Title of host publication36th International Symposium on Computational Geometry, SoCG 2020
    EditorsSergio Cabello, Danny Z. Chen
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    ISBN (Electronic)9783959771436
    DOIs
    StatePublished - Jun 1 2020
    Event36th International Symposium on Computational Geometry, SoCG 2020 - Zurich, Switzerland
    Duration: Jun 23 2020Jun 26 2020

    Publication series

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

    Conference

    Conference36th International Symposium on Computational Geometry, SoCG 2020
    CountrySwitzerland
    CityZurich
    Period6/23/206/26/20

    Keywords

    • 3SUM-hard problems
    • Algebraic decision tree
    • Collinearity testing
    • Polynomial partition
    • Polynomials vanishing on Cartesian products

    ASJC Scopus subject areas

    • Software

    Fingerprint Dive into the research topics of 'Testing polynomials for vanishing on cartesian products of planar point sets'. Together they form a unique fingerprint.

    Cite this