next up previous
Next: Problem 12: Dynamic Planar Up: The Open Problems Project Previous: Problem 10: Simple Linear-Time


Problem 11: 3SUM Hard Problems

Statement
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 aA, bB, and cC such that a + b = c.
Origin
[GO95].
Status/Conjectures
Open.
Motivation
Many fundamental geometric problems fall in this class, e.g., computing the area of the union of n triangles.
Partial and Related Results
Ω(n2) 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

α1x1 + α2x2 + ... + αrxr = α0

where α0, α1, α2,..., αr are fixed constants. Erickson [Eri99a] proved an Ω(n⌈r/2⌉) 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(n2$ \left(\vphantom{\frac{\lg \lg n}{\lg n}}\right.$$ {\frac{{\lg \lg n}}{{\lg n}}}$$ \left.\vphantom{\frac{\lg \lg n}{\lg n}}\right)^{2}_{}$)-time algorithm. With this word size, the 3SUM problem becomes whether any improvement beyond polylogarithmic factors (or indeed, beyond Θ(lg2n)) is possible.

Appearances
[MO01]
Categories
lower bounds
Entry Revision History
J. O'Rourke, 2 Aug. 2001; Jeff Erickson, 20 June 2002; E. Demaine, 7 July 2005; Raphael Clifford, 7 July 2011.

Bibliography

AC05
N. Ailon and B. Chazelle.
Lower bounds for linear degeneracy testing.
Journal of the ACM (JACM), 52(2):157-171, 2005.

BDP05
Ilya Baran, Erik D. Demaine, and Mihai P\normalsize{\v{a\/}}\kern.05emtraşcu.
Subquadratic algorithms for 3SUM.
In Proceedings of the 9th Workshop on Algorithms and Data Structures, Waterloo, Ontario, Canada, August 2005.
To appear.

Eri99a
Jeff Erickson.
Lower bounds for linear satisfiability problems.
Chicago J. Theoret. Comput. Sci., 1999(8), 1999.

Eri99b
Jeff Erickson.
New lower bounds for convex hull problems in odd dimensions.
SIAM J. Comput., 28:1198-1214, 1999.

ES95
Jeff Erickson and R. Seidel.
Better lower bounds on detecting affine and spherical degeneracies.
Discrete Comput. Geom., 13:41-57, 1995.

GO95
A. Gajentaan and M. H. Overmars.
On a class of O(n2) problems in computational geometry.
Comput. Geom. Theory Appl., 5:165-185, 1995.

MO01
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.


next up previous
Next: Problem 12: Dynamic Planar Up: The Open Problems Project Previous: Problem 10: Simple Linear-Time
The Open Problems Project - December 08, 2012