On 3SUM-hard problems in the decision tree model

DOI10.1007/978-3-030-80049-9_16MaRDI QIDQ2117780OpenAlexFDO

Authors Esther Ezra

Publication date 22 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-80049-9_16

zbMATH Keywords

collinearity testing3SUM-hard problemsalgebraic decision tree modelsegment concurrency

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model
• Subquadratic algorithms for some 3Sum-hard geometric problems in the algebraic decision tree model
• Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
• Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets.
• Subquadratic algorithms for algebraic generalizations of 3SUM

Cites work

• scientific article; zbMATH DE number 910895 (Why is no real title available?)
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• Better lower bounds on detecting affine and spherical degeneracies
• CUTTINGS AND APPLICATIONS
• Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
• Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
• Incidence bounds for complex algebraic curves on Cartesian products
• Lower bounds for linear degeneracy testing
• More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
• Near-optimal linear decision trees for k-SUM and related problems
• On a class of \(O(n^ 2)\) problems in computational geometry
• On range searching with semialgebraic sets. II.
• On the Erdős distinct distances problem in the plane
• Point location in arrangements of hyperplanes
• Simplex Range Searching and Its Variants: A Review
• Solving \(k\)-SUM using few linear queries
• Subquadratic algorithms for algebraic generalizations of 3SUM
• Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets.
• Threesomes, degenerates, and love triangles

Cited in

(2)

• Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model
• Subquadratic algorithms for some 3Sum-hard geometric problems in the algebraic decision tree model

This page was built for publication: On 3SUM-hard problems in the decision tree model

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