Improved subquadratic 3SUM

DOI10.1007/s00453-015-0079-6zbMath1359.68130OpenAlexW2178031965WikidataQ56288894 ScholiaQ56288894MaRDI QIDQ513274

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

zbMATH Keywords

3SUMconvolution3SUMZeroTriangle

Mathematics Subject Classification ID

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

Related Items (9)

Geometric pattern matching reduces to \(k\)-SUM ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model ⋮ Time and space efficient collinearity indexing ⋮ A subquadratic algorithm for 3XOR ⋮ Geometric Pattern Matching Reduces to k-SUM. ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy ⋮ Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems

Cites Work

• Unnamed Item
• Unnamed Item
• On a class of \(O(n^ 2)\) problems in computational geometry
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• Subquadratic algorithms for 3SUM
• Pattern Matching under Polynomial Transformation
• Towards polynomial lower bounds for dynamic problems
• Threesomes, Degenerates, and Love Triangles
• Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
• Lower bounds for linear degeneracy testing

This page was built for publication: Improved subquadratic 3SUM