Abstract
We present subquadratic algorithms, in the algebraic decisiontree 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 3SUMhard problem that has so far defied any attempt to obtain a subquadratic solution, whether in the (uniform) real RAM model, or in the algebraic decisiontree model. While we are still unable to solve this problem, in full generality, in subquadratic time, we obtain such a solution, in the algebraic decisiontree model, that uses only roughly O(n^(28/15)) constantdegree polynomial sign tests, for the special case where two of the sets lie on onedimensional 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 unitarea triangle.
This result extends recent work by Barba et al. [Luis Barba et al., 2019] and by Chan [Timothy M. Chan, 2020], where all three sets A, B, and C are assumed to be onedimensional. While there are common features in the highlevel approaches, here and in [Luis Barba et al., 2019], 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 npoint 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(n^(24/13)) constantdegree 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 decisiontree model.
BibTeX  Entry
@InProceedings{aronov_et_al:LIPIcs:2020:12166,
author = {Boris Aronov and Esther Ezra and Micha Sharir},
title = {{Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {8:18:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771436},
ISSN = {18688969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12166},
URN = {urn:nbn:de:0030drops121666},
doi = {10.4230/LIPIcs.SoCG.2020.8},
annote = {Keywords: Algebraic decision tree, Polynomial partition, Collinearity testing, 3SUMhard problems, Polynomials vanishing on Cartesian products}
}
Keywords: 

Algebraic decision tree, Polynomial partition, Collinearity testing, 3SUMhard problems, Polynomials vanishing on Cartesian products 
Collection: 

36th International Symposium on Computational Geometry (SoCG 2020) 
Issue Date: 

2020 
Date of publication: 

08.06.2020 