Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model
type: Item
instance of: scholarly article
title: Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model
author: Boris Aronov
author: Jean Cardinal
author: Esther Ezra
author: John Iacono
author: Mark de Berg
author: Micha Sharir
published in: Computational Geometry
publication date: 2022-11-16T00:00:00Z
full work available at URL: https://arxiv.org/abs/2109.07587
Mathematics Subject Classification ID: 68Qxx
Mathematics Subject Classification ID: 68Uxx
Mathematics Subject Classification ID: 68Pxx
zbMATH DE Number: 7618089
zbMATH Keywords: \textsc{3sum}-hard problems
zbMATH Keywords: algebraic decision-tree model
zbMATH Keywords: point location
zbMATH Keywords: polynomial partitions
zbMATH Keywords: order type
MaRDI profile type: Publication
OpenAlex ID: W3216984471
Wikidata QID: Q114195397
cites work: Partitioning arrangements of lines. II: Applications
cites work: Simplex Range Searching and Its Variants: A Review
cites work: Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
cites work: Q4225298
cites work: Counting Circular Arc Intersections
cites work: Subquadratic algorithms for algebraic 3SUM
cites work: Algorithms in real algebraic geometry
cites work: Q5452284
cites work: CUTTINGS AND APPLICATIONS
cites work: The topological representation of oriented matroids
cites work: On the Folkman-Lawrence topological representation theorem for oriented matroids of rank 3
cites work: Solving k-SUM using few linear queries
cites work: More Logarithmic-factor Speedups for 3SUM, (median,+)-convolution, and Some Geometric 3SUM-hard Problems
cites work: Algorithms for bichromatic line-segment problems and polyhedral terrains
cites work: Fractional cascading. I: A data structuring technique
cites work: Optimal Point Location in a Monotone Subdivision
cites work: Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
cites work: A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
cites work: Oriented matroids
cites work: On a class of \(O(n^ 2)\) problems in computational geometry
cites work: Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy
cites work: Multidimensional Sorting
cites work: Semispaces of configurations, cell complexes of arrangements
cites work: Threesomes, Degenerates, and Love Triangles
cites work: \(\epsilon\)-nets and simplex range queries
cites work: Near-optimal Linear Decision Trees for k-SUM and Related Problems
cites work: Location of a Point in a Planar Subdivision and Its Applications
cites work: Multilevel polynomial partitions and simplified range searching
cites work: Point location in arrangements of hyperplanes
cites work: ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
DOI: 10.1016/J.COMGEO.2022.101945
Recommended article: Q4580085
Recommended article: Subquadratic algorithms for algebraic 3SUM
Recommended article: Subquadratic algorithms for 3SUM
Recommended article: Algorithms and Data Structures
Recommended article: On 3SUM-hard problems in the decision tree model
Recommended article: On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
Recommended article: Subsumption Algorithms for Three-Valued Geometric Resolution
Recommended article: Sublinear geometric algorithms
Recommended article: Sublinear Geometric Algorithms
description: scientific article; zbMATH DE number 7618089