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

zbMATH Open1403.68378MaRDI QIDQ4607939FDOQ4607939

Authors: Timothy M. Chan 

Publication date: 15 March 2018

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

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

Mathematics Subject Classification ID

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

Cited In (9)

• Title not available (Why is that?)
• Subquadratic algorithms for algebraic 3SUM
• Geometric pattern matching reduces to \(k\)-SUM
• Nearly optimal separation between partially and fully retroactive data structures
• Geometric Pattern Matching Reduces to k-SUM.
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• A subquadratic algorithm for 3XOR
• Largest and smallest area triangles on imprecise points
• More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems

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)