Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
DOI10.1007/S00454-022-00437-1OpenAlexW3089561538MaRDI QIDQ2105319FDOQ2105319
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
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
- Efficient partition trees
- On a class of \(O(n^ 2)\) problems in computational geometry
- Title not available (Why is that?)
- Title not available (Why is that?)
- Threesomes, degenerates, and love triangles
- On the Erdős distinct distances problem in the plane
- A deterministic view of random sampling and its use in geometry
- On range searching with semialgebraic sets. II.
- Title not available (Why is that?)
- A combinatorial problem on polynomials and rational functions
- How to find groups?
- Polynomials vanishing on grids: the Elekes-Rónyai problem revisited
- Irreducibility of multivariate polynomials
- Title not available (Why is that?)
- Cutting hyperplanes for divide-and-conquer
- Better lower bounds on detecting affine and spherical degeneracies
- Range searching with efficient hierarchical cuttings
- On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
- Polynomials vanishing on Cartesian products: the Elekes-Szabó theorem revisited
- Improved subquadratic 3SUM
- Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
- Title not available (Why is that?)
- Incidence bounds for complex algebraic curves on Cartesian products
- Almost tight upper bounds for vertical decompositions in four dimensions
- Multilevel polynomial partitions and simplified range searching
- Subquadratic algorithms for algebraic 3SUM
- More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
- Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
- Near-optimal linear decision trees for \(k\)-SUM and related problems
- Geometric pattern matching reduces to \(k\)-SUM
- Constructive polynomial partitioning for algebraic curves in \(\mathbb{R}^3\) with applications
Cited In (4)
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)
