TY - GEN

T1 - More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems

AU - Chan, Timothy M.

N1 - Publisher Copyright:
© Copyright 2018 by SIAM.

PY - 2018

Y1 - 2018

N2 - We present an algorithm that solves the 3SUM problem for n real numbers in O((n2= log2 n)(log log n)O(1)) time, improving previous solutions by about a logarithmic factor. Our framework for shaving o two logarithmic factors can be applied to other problems, such as (median,+)convolution/matrix multiplication and algebraic generalizations of 3SUM. We also obtain 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.

AB - We present an algorithm that solves the 3SUM problem for n real numbers in O((n2= log2 n)(log log n)O(1)) time, improving previous solutions by about a logarithmic factor. Our framework for shaving o two logarithmic factors can be applied to other problems, such as (median,+)convolution/matrix multiplication and algebraic generalizations of 3SUM. We also obtain 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.

UR - http://www.scopus.com/inward/record.url?scp=85045537491&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045537491&partnerID=8YFLogxK

U2 - 10.1137/1.9781611975031.57

DO - 10.1137/1.9781611975031.57

M3 - Conference contribution

AN - SCOPUS:85045537491

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 881

EP - 897

BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

A2 - Czumaj, Artur

PB - Association for Computing Machinery

T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018

Y2 - 7 January 2018 through 10 January 2018

ER -