More Logarithmic-factor Speedups for 3SUM, (median, plus )-convolution, and Some Geometric 3SUM-hard Problems

摘要

This article presents an algorithm that solves the 3SUM problem for n real numbers in O((n(2)/ log(2)n) (log log n)(O(1))) time, improving previous solutions by about a logarithmic factor. Our framework for shaving off two logarithmic factors can be applied to other problems, such as (median,+)-convolution/matrix multiplication and algebraic generalizations of 3SUM. This work also obtains the first subquadratic results on some 3SUM-hard problems in computational geometry, for example, deciding whether (the interiors of) a constant number of simple polygons have a common intersection.