Subquadratic algorithms for algebraic 3SUM
From MaRDI portal
Publication:2415376
DOI10.1007/s00454-018-0040-yzbMath1422.68102OpenAlexW2901785898MaRDI QIDQ2415376
Aurélien Ooms, Stefan Langerman, John Iacono, Noam Solomon, Luis Barba, Jean Cardinal
Publication date: 21 May 2019
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://dipot.ulb.ac.be/dspace/bitstream/2013/283616/3/1612.02384.pdf
algebraic geometryrange searching3SUMdegeneracy testingsubquadratic algorithmsdominance reportinggeneral position testing
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (6)
Geometric pattern matching reduces to \(k\)-SUM ⋮ Time and space efficient collinearity indexing ⋮ Unnamed Item ⋮ Geometric Pattern Matching Reduces to k-SUM. ⋮ Subquadratic algorithms for some \textsc{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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved subquadratic 3SUM
- Necklaces, convolutions, and \(X+Y\)
- Range searching with efficient hierarchical cuttings
- Point location in arrangements of hyperplanes
- On triple intersections of three families of unit circles
- Real quantifier elimination is doubly exponential
- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- Arrangements of curves in the plane --- topology, combinatorics, and algorithms
- How good is the information theory bound in sorting?
- Quantifier elimination and cylindrical algebraic decomposition. Proceedings of a symposium, Linz, Austria, October 6--8, 1993
- The Elekes-Szabó theorem in four dimensions
- New lower bounds for Hopcroft's problem
- Approximations and optimal geometric divide-and-conquer
- On a class of \(O(n^ 2)\) problems in computational geometry
- A combinatorial problem on polynomials and rational functions
- How to find groups?
- Proving simultaneous positivity of linear forms
- On the number of unit-area triangles spanned by convex grids in the plane
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
- Subquadratic algorithms for 3SUM
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
- Polynomials vanishing on grids: The Elekes-Rónyai problem revisited
- Towards polynomial lower bounds for dynamic problems
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- A Lower Bound to Finding Convex Hulls
- Lower bounds for algebraic decision trees
- Constructions in Algebra
- Product Range Spaces, Sensitive Sampling, and Derandomization
- On the Number of Incidences Between Points and Curves
- Threesomes, Degenerates, and Love Triangles
- Higher Lower Bounds from the 3SUM Conjecture
- A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM
- Solving k-SUM using few linear queries
- Schwartz-Zippel bounds for two-dimensional products
- POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
- Derandomization in Computational Geometry
- Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy
- Consequences of Faster Alignment of Sequences
- On Hardness of Jumbled Indexing
- Near-optimal linear decision trees for k-SUM and related problems
- Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited
- The number of unit-area triangles in the plane: Theme and variations
- Lower bounds for linear degeneracy testing
- Algorithms in real algebraic geometry
This page was built for publication: Subquadratic algorithms for algebraic 3SUM
