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.
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(n^2 \left(\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 \Theta(\lg^2 n)) is possible.
lower bounds
J. O’Rourke, 2 Aug. 2001; Jeff Erickson, 20 June 2002; E. Demaine, 7 July 2005; Raphael Clifford, 7 July 2011.
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.
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.
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.