Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model

DOI10.1016/j.comgeo.2022.101945OpenAlexW3216984471WikidataQ114195397 ScholiaQ114195397MaRDI QIDQ2096389

John Iacono, Jean Cardinal, Boris Aronov, Esther Ezra, Micha Sharir, Mark T. de Berg

Publication date: 16 November 2022

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2109.07587

zbMATH Keywords

order typepoint location\textsc{3sum}-hard problemsalgebraic decision-tree modelpolynomial partitions

Mathematics Subject Classification ID

Theory of data (68Pxx) Theory of computing (68Qxx) Computing methodologies and applications (68Uxx)

Related Items (1)

Time and space efficient collinearity indexing

Cites Work

• Unnamed Item
• Unnamed Item
• Point location in arrangements of hyperplanes
• Semispaces of configurations, cell complexes of arrangements
• Partitioning arrangements of lines. II: Applications
• \(\epsilon\)-nets and simplex range queries
• Fractional cascading. I: A data structuring technique
• Oriented matroids
• Algorithms for bichromatic line-segment problems and polyhedral terrains
• On a class of \(O(n^ 2)\) problems in computational geometry
• Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
• Multilevel polynomial partitions and simplified range searching
• Subquadratic algorithms for algebraic 3SUM
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• The topological representation of oriented matroids
• Multidimensional Sorting
• Counting Circular Arc Intersections
• Optimal Point Location in a Monotone Subdivision
• Location of a Point in a Planar Subdivision and Its Applications
• Threesomes, Degenerates, and Love Triangles
• Simplex Range Searching and Its Variants: A Review
• Solving k-SUM using few linear queries
• CUTTINGS AND APPLICATIONS
• 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
• ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
• Near-optimal Linear Decision Trees for k-SUM and Related Problems
• Algorithms in real algebraic geometry
• On the Folkman-Lawrence topological representation theorem for oriented matroids of rank 3

This page was built for publication: Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model