TY - JOUR

T1 - Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets

T2 - Collinearity Testing and Related Problems

AU - Aronov, Boris

AU - Ezra, Esther

AU - Sharir, Micha

N1 - Funding Information:
The authors wish to thank Adam Sheffer and Frank de Zeeuw for suggesting the transformation used for collinearity testing in Theorem . This has considerably simplified and shortened our original analysis for the “flat” case. We also thank Jean Cardinal, John Iacono, Stefan Langerman, and Aurélien Ooms for useful discussions on the relation of our work with that in []. A preliminary version of this paper [] has appeared in proceedings of the 36th Annual Symposium on Computational Geometry (2020). Work by Boris Aronov was partially supported by NSF Grant CCF-15-40656 and by Grant 2014/170 from the US–Israel Binational Science Foundation. Work by Esther Ezra was partially supported by NSF CAREER under Grant CCF:AF-1553354 and by Grant 824/17 from the Israel Science Foundation. Work by Micha Sharir was partially supported by ISF Grant 260/18, by Grant 1367/2016 from the German–Israeli Science Foundation (GIF), and by Blavatnik Research Fund in Computer Science at Tel Aviv University.
Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2022/12

Y1 - 2022/12

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

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

KW - Algebraic decision trees

KW - Collinearity testing

KW - Polynomial partitioning

KW - Semi-algebraic range searching

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

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

U2 - 10.1007/s00454-022-00437-1

DO - 10.1007/s00454-022-00437-1

M3 - Article

AN - SCOPUS:85138450442

SN - 0179-5376

VL - 68

SP - 997

EP - 1048

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 4

ER -