Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
From MaRDI portal
Publication:2105319
DOI10.1007/s00454-022-00437-1OpenAlexW3089561538MaRDI QIDQ2105319
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
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Erd?s problems and related topics of discrete geometry (52C10) Data structures (68P05) Combinatorial complexity of geometric structures (52C45) Computational real algebraic geometry (14Q30)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the Erdős distinct distances problem in the plane
- Polynomials vanishing on Cartesian products: the Elekes-Szabó theorem revisited
- Improved subquadratic 3SUM
- Range searching with efficient hierarchical cuttings
- A deterministic view of random sampling and its use in geometry
- On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
- Irreducibility of multivariate polynomials
- Efficient partition trees
- Cutting hyperplanes for divide-and-conquer
- Better lower bounds on detecting affine and spherical degeneracies
- On a class of \(O(n^ 2)\) problems in computational geometry
- A combinatorial problem on polynomials and rational functions
- Geometric pattern matching reduces to \(k\)-SUM
- How to find groups?
- Multilevel polynomial partitions and simplified range searching
- Subquadratic algorithms for algebraic 3SUM
- Incidence bounds for complex algebraic curves on Cartesian products
- Polynomials vanishing on grids: The Elekes-Rónyai problem revisited
- Almost tight upper bounds for vertical decompositions in four dimensions
- Threesomes, Degenerates, and Love Triangles
- More Logarithmic-factor Speedups for 3SUM, (median,+)-convolution, and Some Geometric 3SUM-hard Problems
- Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
- Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy
- Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications
- Near-optimal Linear Decision Trees for k-SUM and Related Problems
- On Range Searching with Semialgebraic Sets. II
