Subquadratic algorithms for some 3Sum-hard geometric problems in the algebraic decision tree model

DOI10.4230/LIPICS.ISAAC.2021.3MaRDI QIDQ6187787FDOQ6187787

Authors: Boris Aronov, Mark de Berg, Jean Cardinal, Esther Ezra, John Iacono, Micha Sharir 

Publication date: 15 January 2024

Recommendations

• Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model
• On 3SUM-hard problems in the decision tree model
• Subquadratic algorithms for algebraic generalizations of 3SUM
• Subquadratic algorithms for algebraic 3SUM
• On a class of \(O(n^2)\) problems in computational geometry

zbMATH Keywords

computational geometrypoint locationpolynomial partitioningorder typeshierarchical partitionsalgebraic decision-tree modelprimal-dual range searching

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

This page was built for publication: Subquadratic algorithms for some 3Sum-hard geometric problems in the algebraic decision tree model

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