TY - GEN

T1 - Subquadratic algorithms for algebraic generalizations of 3SUM

AU - Barba, Luis

AU - Cardinal, Jean

AU - Iacono, John

AU - Langerman, Stefan

AU - Ooms, Aurélien

AU - Solomon, Noam

N1 - Funding Information:
∗Supported by the “Action de Recherche Concertée” (ARC) COPHYMA, convention number 4.110.H.000023. † Research partially completed while on sabbatical at the Algorithms Research Group of the Département d’Informatique at the Université libre de Bruxelles with support from a Fulbright Research Fellowship, the Fonds de la Recherche Scientifique – FNRS, and NSF grants CNS-1229185, CCF-1319648, and CCF-1533564. ‡ Directeur de recherches du F.R.S.-FNRS. § Supported by the Fund for Research Training in Industry and Agriculture (FRIA). ¶ Supported by Grant 892/13 from the Israel Science Foundation.

PY - 2017/6/1

Y1 - 2017/6/1

N2 - The 3SUM problem asks if an input n-set of real numbers contains a triple whose sum is zero. We consider the 3POL problem, a natural generalization of 3SUM where we replace the sum function by a constant-degree polynomial in three variables. The motivations are threefold. Raz, Sharir, and de Zeeuw gave an O(n11/6) upper bound on the number of solutions of trivariate polynomial equations when the solutions are taken from the cartesian product of three n-sets of real numbers. We give algorithms for the corresponding problem of counting such solutions. Grønlund and Pettie recently designed subquadratic algorithms for 3SUM. We generalize their results to 3POL. Finally, we shed light on the General Position Testing (GPT) problem: "Given n points in the plane, do three of them lie on a line?", a key problem in computational geometry. We prove that there exist bounded-degree algebraic decision trees of depth O(n12/7+ϵ) that solve 3POL, and that 3POL can be solved in O(n2(log log n)3/2/(log n)1/2) time in the real-RAM model. Among the possible applications of those results, we show how to solve GPT in sub-quadratic time when the input points lie on o((log n)1/6/(log log n)1/2) constant-degree polynomial curves. This constitutes the first step towards closing the major open question of whether GPT can be solved in subquadratic time. To obtain these results, we generalize important tools - such as batch range searching and dominance reporting - to a polynomial setting. We expect these new tools to be useful in other applications.

AB - The 3SUM problem asks if an input n-set of real numbers contains a triple whose sum is zero. We consider the 3POL problem, a natural generalization of 3SUM where we replace the sum function by a constant-degree polynomial in three variables. The motivations are threefold. Raz, Sharir, and de Zeeuw gave an O(n11/6) upper bound on the number of solutions of trivariate polynomial equations when the solutions are taken from the cartesian product of three n-sets of real numbers. We give algorithms for the corresponding problem of counting such solutions. Grønlund and Pettie recently designed subquadratic algorithms for 3SUM. We generalize their results to 3POL. Finally, we shed light on the General Position Testing (GPT) problem: "Given n points in the plane, do three of them lie on a line?", a key problem in computational geometry. We prove that there exist bounded-degree algebraic decision trees of depth O(n12/7+ϵ) that solve 3POL, and that 3POL can be solved in O(n2(log log n)3/2/(log n)1/2) time in the real-RAM model. Among the possible applications of those results, we show how to solve GPT in sub-quadratic time when the input points lie on o((log n)1/6/(log log n)1/2) constant-degree polynomial curves. This constitutes the first step towards closing the major open question of whether GPT can be solved in subquadratic time. To obtain these results, we generalize important tools - such as batch range searching and dominance reporting - to a polynomial setting. We expect these new tools to be useful in other applications.

KW - 3SUM

KW - Dominance reporting

KW - General position testing

KW - Polynomial curves

KW - Range searching

KW - Subquadratic algorithms

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

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

U2 - 10.4230/LIPIcs.SoCG.2017.13

DO - 10.4230/LIPIcs.SoCG.2017.13

M3 - Conference contribution

AN - SCOPUS:85029939658

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 131

EP - 1315

BT - 33rd International Symposium on Computational Geometry, SoCG 2017

A2 - Katz, Matthew J.

A2 - Aronov, Boris

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 33rd International Symposium on Computational Geometry, SoCG 2017

Y2 - 4 July 2017 through 7 July 2017

ER -