On 3SUM-hard problems in the decision tree model

DOI10.1007/978-3-030-80049-9_16OpenAlexW3178116731MaRDI QIDQ2117780FDOQ2117780

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On a class of \(O(n^ 2)\) problems in computational geometry
• Threesomes, Degenerates, and Love Triangles
• On the Erdős distinct distances problem in the plane
• Lower bounds for linear degeneracy testing
• CUTTINGS AND APPLICATIONS
• On Range Searching with Semialgebraic Sets. II
• Point location in arrangements of hyperplanes
• Better lower bounds on detecting affine and spherical degeneracies
• Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• Incidence bounds for complex algebraic curves on Cartesian products
• Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets.
• Simplex Range Searching and Its Variants: A Review
• Solving k-SUM using few linear queries
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
• 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

Cited In (1)

• Subquadratic algorithms for some \textsc{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)