Document Open Access Logo

Subquadratic Algorithms for Algebraic Generalizations of 3SUM

Authors Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, Noam Solomon

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.13.pdf
  • Filesize: 1.02 MB
  • 15 pages

Document Identifiers

Author Details

Luis Barba
Jean Cardinal
John Iacono
Stefan Langerman
Aurélien Ooms
Noam Solomon

Cite As Get BibTex

Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, and Noam Solomon. Subquadratic Algorithms for Algebraic Generalizations of 3SUM. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SoCG.2017.13

Abstract

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(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 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(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 real-RAM 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}) 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.

Subject Classification

Keywords
  • 3SUM
  • subquadratic algorithms
  • general position testing
  • range searching
  • dominance reporting
  • polynomial curves

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In FOCS, pages 434-443. IEEE Computer Society, 2014. Google Scholar
  2. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In ICALP (1), volume 8572 of LNCS, pages 39-51, 2014. Google Scholar
  3. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In STOC, pages 41-50. ACM, 2015. Google Scholar
  4. Nir Ailon and Bernard Chazelle. Lower bounds for linear degeneracy testing. J. ACM, 52(2):157-171, 2005. Google Scholar
  5. Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. On hardness of jumbled indexing. In ICALP (1), volume 8572 of LNCS, pages 114-125, 2014. Google Scholar
  6. Ilya Baran, Erik D. Demaine, and Mihai Pătrascu. Subquadratic algorithms for 3SUM. Algorithmica, 50(4):584-596, 2008. Google Scholar
  7. Gill Barequet and Sariel Har-Peled. Polygon containment and translational min Hausdorff distance between segment sets are 3SUM-hard. Int. J. Comput. Geometry Appl., 11(4):465-474, 2001. Google Scholar
  8. Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Computing roadmaps of semi-algebraic sets (extended abstract). In STOC, pages 168-173. ACM, 1996. Google Scholar
  9. Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in real algebraic geometry, volume 10 of Algorithms and Computation in Mathematics. Springer, 2006. Google Scholar
  10. David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, and Perouz Taslakian. Necklaces, Convolutions, and X+Y. Algorithmica, 69(2):294-314, 2014. Google Scholar
  11. Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In ITCS, pages 261-270. ACM, 2016. Google Scholar
  12. Bob F. Caviness and Jeremy R. Johnson. Quantifier elimination and cylindrical algebraic decomposition. Springer, 2012. Google Scholar
  13. Timothy M. Chan. All-pairs shortest paths with real weights in O(n³/log n) time. Algorithmica, 50(2):236-243, 2008. Google Scholar
  14. George E. Collins. Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In Automata Theory and Formal Languages, volume 33 of LNCS, pages 134-183. Springer, 1975. Google Scholar
  15. James H. Davenport and Joos Heintz. Real quantifier elimination is doubly exponential. J. Symb. Comput., 5(1/2):29-35, 1988. Google Scholar
  16. György Elekes and Lajos Rónyai. A combinatorial problem on polynomials and rational functions. J. Comb. Theory, Ser. A, 89(1):1-20, 2000. Google Scholar
  17. György Elekes and Endre Szabó. How to find groups? (and how to use them in Erdős geometry?). Combinatorica, 32(5):537-571, 2012. Google Scholar
  18. Jeff Erickson. Lower bounds for linear satisfiability problems. Chicago J. Theor. Comput. Sci., 1999. Google Scholar
  19. Michael L. Fredman. How good is the information theory bound in sorting? Theor. Comput. Sci., 1(4):355-361, 1976. Google Scholar
  20. Ari Freund. Improved subquadratic 3SUM. Algorithmica, pages 1-19, 2015. Google Scholar
  21. Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Comput. Geom., 5:165-185, 1995. Google Scholar
  22. Omer Gold and Micha Sharir. Improved bounds for 3SUM, k-SUM, and linear degeneracy. ArXiv e-prints, 2015. URL: https://arxiv.org/abs/1512.05279.
  23. Allan Grønlund and Seth Pettie. Threesomes, degenerates, and love triangles. In Foundations of Computer Science (FOCS 2014), pages 621-630. IEEE, 2014. Google Scholar
  24. Joe Harris. Algebraic geometry: a first course, volume 133. Springer, 2013. Google Scholar
  25. Robin Hartshorne. Algebraic geometry, volume 52. Springer, 1977. Google Scholar
  26. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In STOC, pages 21-30. ACM, 2015. Google Scholar
  27. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3SUM conjecture. In SODA, pages 1272-1287. SIAM, 2016. Google Scholar
  28. Jirí Matoušek. Range searching with efficient hierarchical cutting. Discrete & Computational Geometry, 10:157-182, 1993. Google Scholar
  29. Bhubaneswar Mishra. Computational real algebraic geometry. In Handbook of Discrete and Computational Geometry, 2nd Ed., pages 743-764. Chapman and Hall/CRC, 2004. Google Scholar
  30. H. Nassajian Mojarrad, T. Pham, C. Valculescu, and F. de Zeeuw. Schwartz-Zippel bounds for two-dimensional products. ArXiv e-prints, 2016. URL: https://arxiv.org/abs/1507.08181.
  31. János Pach and Micha Sharir. On the number of incidences between points and curves. Combinatorics, Probability & Computing, 7(1):121-127, 1998. Google Scholar
  32. Mihai Pătrascu. Towards polynomial lower bounds for dynamic problems. In STOC, pages 603-610. ACM, 2010. Google Scholar
  33. Franco P. Preparata and Michael Ian Shamos. Computational Geometry - An Introduction. Texts and Monographs in Computer Science. Springer, 1985. Google Scholar
  34. Michael O. Rabin. Proving simultaneous positivity of linear forms. J. Comput. Syst. Sci., 6(6):639-650, 1972. Google Scholar
  35. Orit E. Raz, Micha Sharir, and Frank de Zeeuw. Polynomials vanishing on cartesian products: The Elekes-Szabó theorem revisited. In SoCG, volume 34 of LIPIcs, pages 522-536, 2015. Google Scholar
  36. Orit E. Raz, Micha Sharir, and Frank de Zeeuw. The elekes-szabó theorem in four dimensions. ArXiv e-prints, 2016. URL: https://arxiv.org/abs/1607.03600.
  37. Orit E. Raz, Micha Sharir, and József Solymosi. Polynomials vanishing on grids: The Elekes-Rónyai problem revisited. In SoCG, page 251. ACM, 2014. Google Scholar
  38. Abraham Seidenberg. Constructions in algebra. Transactions of the AMS, 197:273-313, 1974. Google Scholar
  39. J. Michael Steele and Andrew Yao. Lower bounds for algebraic decision trees. J. Algorithms, 3(1):1-8, 1982. Google Scholar
  40. Alfred Tarski. A decision method for elementary algebra and geometry, 1951. Rand Corporation. Google Scholar
  41. Andrew Yao. A lower bound to finding convex hulls. J. ACM, 28(4):780-787, 1981. Google Scholar
  42. David Yun. On square-free decomposition algorithms. In SYMSACC, pages 26-35, 1976. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact