Improved subquadratic 3SUM

DOI10.1007/S00453-015-0079-6zbMATH Open1359.68130DBLPjournals/algorithmica/Freund17OpenAlexW2178031965WikidataQ56288894 ScholiaQ56288894MaRDI QIDQ513274FDOQ513274

Authors: Ari Freund 

Publication date: 3 March 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-015-0079-6

Recommendations

• Algorithms and Data Structures
• Threesomes, degenerates, and love triangles
• Subquadratic algorithms for 3SUM
• Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
• Subquadratic algorithms for algebraic 3SUM

zbMATH Keywords

3SUMconvolution3SUMZeroTriangle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Nonnumerical algorithms (68W05)

Cites Work

• On a class of \(O(n^ 2)\) problems in computational geometry
• Subquadratic algorithms for 3SUM
• Towards polynomial lower bounds for dynamic problems
• Title not available (Why is that?)
• Threesomes, degenerates, and love triangles
• Lower bounds for linear degeneracy testing
• Speeding up the four Russians algorithm by about one more logarithmic factor
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• Pattern matching under polynomial transformation
• Title not available (Why is that?)

Cited In (16)

• Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
• Subquadratic algorithms for algebraic 3SUM
• 3SUM, 3XOR, triangles
• Geometric pattern matching reduces to \(k\)-SUM
• Geometric Pattern Matching Reduces to k-SUM.
• Threesomes, degenerates, and love triangles
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• Algorithms and Data Structures
• Subquadratic algorithms for 3SUM
• Time and space efficient collinearity indexing
• A subquadratic algorithm for 3XOR
• More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
• Subquadratic algorithms for algebraic generalizations of 3SUM
• Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
• Connectivity oracles for graphs subject to vertex failures
• More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems

This page was built for publication: Improved subquadratic 3SUM

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