Barba, Luis ;
Cardinal, Jean ;
Iacono, John ;
Langerman, Stefan ;
Ooms, Aurélien ;
Solomon, Noam
Subquadratic Algorithms for Algebraic Generalizations of 3SUM
Abstract
The 3SUM problem asks if an input nset 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 constantdegree polynomial in three variables. The motivations are threefold. Raz, Sharir, and de Zeeuw gave an O(n^{11/6}) upper bound on the number of solutions of trivariate polynomial equations when the solutions are taken from the cartesian product of three nsets 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 boundeddegree algebraic decision trees of depth O(n^{12/7+e}) that solve 3POL, and that 3POL can be solved in O(n^2 (log log n)^{3/2} / (log n)^{1/2}) time in the realRAM model. Among the possible applications of those results, we show how to solve GPT in subquadratic time when the input points lie on o((log n)^{1/6}/(log log n)^{1/2}) constantdegree 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.
BibTeX  Entry
@InProceedings{barba_et_al:LIPIcs:2017:7221,
author = {Luis Barba and Jean Cardinal and John Iacono and Stefan Langerman and Aur{\'e}lien Ooms and Noam Solomon},
title = {{Subquadratic Algorithms for Algebraic Generalizations of 3SUM}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {13:113:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770385},
ISSN = {18688969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7221},
URN = {urn:nbn:de:0030drops72214},
doi = {10.4230/LIPIcs.SoCG.2017.13},
annote = {Keywords: 3SUM, subquadratic algorithms, general position testing, range searching, dominance reporting, polynomial curves}
}
20.06.2017
Keywords: 

3SUM, subquadratic algorithms, general position testing, range searching, dominance reporting, polynomial curves 
Seminar: 

33rd International Symposium on Computational Geometry (SoCG 2017)

Issue date: 

2017 
Date of publication: 

20.06.2017 