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

MaRDI QIDQ4607939zbMATHFDO

Authors Timothy M. Chan

Publication date 15 March 2018

Full work available at URL http://dl.acm.org/citation.cfm?id=3175327

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
• Improved subquadratic 3SUM
• Algorithms and Data Structures
• Subquadratic algorithms for 3SUM
• Clustered Integer 3SUM via Additive Combinatorics

Cited in

(9)

• A subquadratic algorithm for 3XOR
• Largest and smallest area triangles on imprecise points
• Geometric pattern matching reduces to \(k\)-SUM
• More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
• Nearly optimal separation between partially and fully retroactive data structures
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• Geometric Pattern Matching Reduces to k-SUM.
• Subquadratic algorithms for algebraic 3SUM
• On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress

This page was built for publication: More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607939)