Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets: Collinearity Testing and Related Problems

Boris Aronov, Esther Ezra, Micha Sharir

    Research output: Contribution to journalArticlepeer-review

    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 roughly O(n28 / 15) constant-degree polynomial sign tests, for the special case where two of the sets lie on two respective one-dimensional curves and the third is placed arbitrarily in the plane. Our technique is fairly general, and applies to many other problems 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. (2017) and by Chan (2018), where all three sets A, B, and C are assumed to be one-dimensional. 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 independent real polynomial equations. For example, this is the setup when testing for collinearity in the complex plane, when each of the sets A, B, C lies on some constant-degree algebraic curve. We show that problems of this kind can be solved with roughly O(n24 / 13) constant-degree polynomial sign tests.

    Original languageEnglish (US)
    JournalDiscrete and Computational Geometry
    DOIs
    StateAccepted/In press - 2022

    Keywords

    • Algebraic decision trees
    • Collinearity testing
    • Polynomial partitioning
    • Semi-algebraic range searching

    ASJC Scopus subject areas

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

    Fingerprint

    Dive into the research topics of 'Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets: Collinearity Testing and Related Problems'. Together they form a unique fingerprint.

    Cite this