Improved algebraic degeneracy testing

DOI10.1007/S00454-024-00673-7MaRDI QIDQ6963480zbMATH OpenFDO

Authors Jean Cardinal, Micha Sharir

Publication date 7 July 2025

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

Full work available at URL https://doi.org/10.1007/S00454-024-00673-7

zbMATH Keywords

\(k\)-SUM problembolynomial methoddegeneracy testingHopcroft's problemincidence bounds

Mathematics Subject Classification ID

Computational aspects of algebraic surfaces (14Q10) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Cites work

• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• A semi-algebraic version of Zarankiewicz's problem
• Algorithms in real algebraic geometry
• All non-trivial variants of 3-LDT are equivalent
• Better lower bounds on detecting affine and spherical degeneracies
• Computational geometry. Algorithms and applications.
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Deterministic time-space trade-offs for k-SUM
• Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Geometric pattern matching reduces to \(k\)-SUM
• Hopcroft's problem, log-star shaving, 2D fractional cascading, and decision trees
• How good is the information theory bound in sorting?
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 1351079 (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
• Intersection queries for flat semi-algebraic objects in three dimensions and related problems
• Intersection searching amid tetrahedra in 4-space and efficient continuous collision detection
• Location of a Point in a Planar Subdivision and Its Applications
• Lower bounds for algebraic decision trees
• Lower bounds for linear degeneracy testing
• 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
• New Bounds on the Complexity of the Shortest Path Problem
• On a class of \(O(n^ 2)\) problems in computational geometry
• On some fine-grained questions in algorithms and complexity
• On the Optimality of Some Set Algorithms
• On the possibility of faster \textsc{SAT} algorithms
• Optimal Point Location in a Monotone Subdivision
• Point location in arrangements of hyperplanes
• Range searching with efficient hierarchical cuttings
• Reducing \textsf{3SUM} to \textsf{Convolution-3SUM}
• Simplex Range Searching and Its Variants: A Review
• Solving k-SUM using few linear queries
• Subquadratic algorithms for 3SUM
• Subquadratic algorithms for algebraic 3SUM
• Subquadratic algorithms for some 3Sum-hard geometric problems in the algebraic decision tree model
• Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
• Threesomes, degenerates, and love triangles

Cited in

(1)

• Compact representation of semilinear and terrain-like graphs

This page was built for publication: Improved algebraic degeneracy testing

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