Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems

DOI10.1007/S00454-022-00437-1MaRDI QIDQ2105319zbMATH OpenOpenAlexFDO

Authors Boris Aronov, Esther Ezra, Micha Sharir

Publication date 8 December 2022

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.09533

zbMATH Keywords

algebraic decision treescollinearity testingpolynomial partitioningsemi-algebraic range searching

Mathematics Subject Classification ID

Computational real algebraic geometry (14Q30) Erd?s problems and related topics of discrete geometry (52C10) Combinatorial complexity of geometric structures (52C45) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Subquadratic algorithms for algebraic generalizations of 3SUM
• Subquadratic algorithms for algebraic 3SUM
• Polynomials vanishing on Cartesian products: the Elekes-Szabó theorem revisited
• Threesomes, degenerates, and love triangles
• On a class of \(O(n^ 2)\) problems in computational geometry

Cites work

• A combinatorial problem on polynomials and rational functions
• A deterministic view of random sampling and its use in geometry
• Almost tight upper bounds for vertical decompositions in four dimensions
• Better lower bounds on detecting affine and spherical degeneracies
• Constructive polynomial partitioning for algebraic curves in \(\mathbb{R}^3\) with applications
• Cutting hyperplanes for divide-and-conquer
• Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
• Efficient partition trees
• Geometric pattern matching reduces to \(k\)-SUM
• How to find groups?
• scientific article; zbMATH DE number 4151829 (Why is no real title available?)
• scientific article; zbMATH DE number 3823145 (Why is no real title available?)
• scientific article; zbMATH DE number 4029737 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3497890 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
• Improved subquadratic 3SUM
• Incidence bounds for complex algebraic curves on Cartesian products
• Irreducibility of multivariate polynomials
• More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
• Multilevel polynomial partitions and simplified range searching
• 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 Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• On the Erdős distinct distances problem in the plane
• Polynomials vanishing on Cartesian products: the Elekes-Szabó theorem revisited
• Range searching with efficient hierarchical cuttings
• Subquadratic algorithms for algebraic 3SUM
• Threesomes, degenerates, and love triangles

Cited in

(6)

• On 3SUM-hard problems in the decision tree model
• Time and space efficient collinearity indexing
• On a class of O(n^2) problems in computational geometry
• Subquadratic algorithms for algebraic generalizations of 3SUM
• Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets.
• Improved algebraic degeneracy testing

This page was built for publication: Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems

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