Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
type: Item
instance of: scholarly article
title: Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
author: Boris Aronov
author: Esther Ezra
author: Micha Sharir
published in: Discrete \& Computational Geometry
publication date: 2022-12-08T00:00:00Z
full work available at URL: https://arxiv.org/abs/2003.09533
Mathematics Subject Classification ID: 14Q30
Mathematics Subject Classification ID: 52C10
Mathematics Subject Classification ID: 52C45
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 7628954
zbMATH Keywords: polynomial partitioning
zbMATH Keywords: collinearity testing
zbMATH Keywords: algebraic decision trees
zbMATH Keywords: semi-algebraic range searching
MaRDI profile type: Publication
OpenAlex ID: W3089561538
cites work: Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
cites work: On Range Searching with Semialgebraic Sets. II
cites work: Geometric pattern matching reduces to \(k\)-SUM
cites work: Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications
cites work: Subquadratic algorithms for algebraic 3SUM
cites work: Q3770650
cites work: More Logarithmic-factor Speedups for 3SUM, (median,+)-convolution, and Some Geometric 3SUM-hard Problems
cites work: Cutting hyperplanes for divide-and-conquer
cites work: Q3481216
cites work: A deterministic view of random sampling and its use in geometry
cites work: Q4079605
cites work: Q3413659
cites work: A combinatorial problem on polynomials and rational functions
cites work: How to find groups?
cites work: Better lower bounds on detecting affine and spherical degeneracies
cites work: Improved subquadratic 3SUM
cites work: On a class of \(O(n^ 2)\) problems in computational geometry
cites work: Irreducibility of multivariate polynomials
cites work: Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy
cites work: Threesomes, Degenerates, and Love Triangles
cites work: On the Erdős distinct distances problem in the plane
cites work: Q3668871
cites work: Near-optimal Linear Decision Trees for k-SUM and Related Problems
cites work: Almost tight upper bounds for vertical decompositions in four dimensions
cites work: Efficient partition trees
cites work: Range searching with efficient hierarchical cuttings
cites work: Multilevel polynomial partitions and simplified range searching
cites work: Q3992847
cites work: Polynomials vanishing on Cartesian products: the Elekes-Szabó theorem revisited
cites work: Polynomials vanishing on grids: the Elekes-Rónyai problem revisited
cites work: On the ''Piano Movers'' problem. II: General techniques for computing topological properties of real algebraic manifolds
cites work: Q4325546
cites work: Incidence bounds for complex algebraic curves on Cartesian products
DOI: 10.1007/S00454-022-00437-1
description: scientific article; zbMATH DE number 7628954