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 treespolynomial partitioningcollinearity testingsemi-algebraic range searching

Mathematics Subject Classification ID

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

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

• 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?)
• 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?
• 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

(4)

• Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets.
• On a class of \(O(n^2)\) problems in computational geometry
• Subquadratic algorithms for algebraic generalizations of 3SUM
• Time and space efficient collinearity indexing

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)