Next: Problem 12: Dynamic Planar Convex Hull
Previous: Problem 10: Simple Linear-Time Polygon Triangulation
Can the class of 3SUM hard problems be solved in subquadratic time? These problems can be reduced from the problem of determining whether, given three sets of integers, A, B, and C with total size n, there are elements a \in A, b \in B, and c \in C such that a+b=c.
Open. Subquadratic time algorithms have been found (see [GP14], [GS17], [Cha18]), but it is conjectured that 3SUM is unsolvable in O(n^{2-\epsilon}) time, even in expectation [KPP16].
Many fundamental geometric problems fall in this class, e.g., computing the area of the union of n triangles.
\Omega(n^2) lower bounds are known for 3SUM and a few 3SUM-hard problems in restricted decision tree models of computation [ES95], [Eri99a], [Eri99b].
3SUM and its obvious generalizations (4SUM, 5SUM, etc.) are examples of linear satisfiability problems. A generic linear satisfiability problem asks, given an array of n integers, do any r of them satisfy the equation \alpha_1 x_1 + \alpha_2 x_2 + \cdots + \alpha_r x_r = \alpha_0 where \alpha_0, \alpha_1, \alpha_2, \dots, \alpha_r are fixed constants. Erickson [Eri99a] proved an \Omega(n^{\lceil r/2 \rceil}) lower bound for any problem of this type, in the restricted linear decision tree model. This lower bound is tight except for a logarithmic factor when r is even. Ailon and Chazelle generalized Erickson’s bound and improve it for large r or for more than r variables [AC05].
Baran et al. [BDP05] show that subquadratic algorithms for 3SUM are possible in common models of computation that allow more direct manipulation of the numbers instead of just real arithmetic, such as the word RAM. The improvement they obtain is roughly quadratic in the parallelism offered by the model; for example, with \lg n-bit words, they obtain an O\left(n^2 \left(\frac{\lg \lg n}{\lg n}\right)^2\right)-time algorithm.
Grønlund and Pettie [GP14] gave the first subquadratic deterministic algorithm in the standard real-RAM model that solves 3SUM in O\left(n^2 \left(\frac{\lg \lg n}{\lg n}\right)^{2/3}\right) time. Gold and Sharir [GS17] improved this to O\left(\frac{n^2 \lg \lg n}{\lg n}\right), and then Chan [Cha18] shaved off a nearly logarithmic factor to obtain an O\left(\frac{n^2 \left(\lg \lg n\right)^{O(1)}}{\lg^2 n}\right)-time algorithm.
lower bounds
J. O’Rourke, 2 Aug. 2001; Jeff Erickson, 20 June 2002; E. Demaine, 7 July 2005; Raphael Clifford, 7 July 2011; J. Mallen, 18 June 2025.
N. Ailon and B. Chazelle. Lower bounds for linear degeneracy testing. Journal of the ACM, 52(2):157–171, 2005.
Ilya Baran, Erik D. Demaine, and Mihai Pǎtraşcu. . In Proceedings of the 9th Workshop on Algorithms and Data Structures, volume 3608 of Lecture Notes in Computer Science, pages 409–421, Waterloo, Ontario, Canada, August 2005.
Timothy M. Chan. More logarithmic-factor speedups for 3sum, (median,+)-convolution, and some geometric 3sum-hard problems. In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 881–897, 2018.
Jeff Erickson. Lower bounds for linear satisfiability problems. Chicago J. Theoret. Comput. Sci., 1999(8), 1999.
Jeff Erickson. New lower bounds for convex hull problems in odd dimensions. SIAM J. Comput., 28:1198–1214, 1999.
Jeff Erickson and R. Seidel. Better lower bounds on detecting affine and spherical degeneracies. Discrete Comput. Geom., 13:41–57, 1995.
A. Gajentaan and M. H. Overmars. On a class of {O}(n^2) problems in computational geometry. Comput. Geom. Theory Appl., 5:165–185, 1995.
Allan Grønlund and Seth Pettie. Threesomes, degenerates, and love triangles. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pages 621–630, Los Alamitos, CA, USA, Oct 2014. IEEE Computer Society.
Omer Gold and Micha Sharir. Improved bounds for 3sum, k-sum, and linear degeneracy. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms (ESA 2017), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1–42:13, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1272–1287. SIAM, 2016.
J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42. Internat. J. Comput. Geom. Appl., 11(5):573–582, 2001. Also in SIGACT News 32(3):63-72 (2001), Issue 120.