Multilevel polynomial partitions and simplified range searching
From MaRDI portal
Publication:2354673
DOI10.1007/s00454-015-9701-2zbMath1332.68266arXiv1406.3058OpenAlexW1862680590MaRDI QIDQ2354673
Ji{ří} Matoušek, Zuzana Safernová
Publication date: 20 July 2015
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1406.3058
Related Items
A semi-algebraic version of Zarankiewicz's problem, \(L^2\) bounds for a maximal directional Hilbert transform, Cutting algebraic curves into pseudo-segments and applications, Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning, On reverse shortest paths in geometric proximity graphs, Throwing a sofa through the window, On semialgebraic range reporting, Simplex Range Searching and Its Variants: A Review, Few cuts meet many point sets, The polynomial method over varieties, Unnamed Item, On a real analog of Bezout inequality and the number of connected components of sign conditions, Polynomial partitioning on varieties of codimension two and point-hypersurface incidences in four dimensions, Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications, On the Stretch Factor of Polygonal Chains, Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model, Maximal directional operators along algebraic varieties, 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
- Refined bounds on the number of connected components of sign conditions on a variety
- Optimal partition trees
- An incidence theorem in higher dimensions
- On the Erdős distinct distances problem in the plane
- Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
- A Szemerédi-Trotter type theorem in \(\mathbb R^4\)
- Elementary structure of real algebraic varieties
- Definability and fast quantifier elimination in algebraically closed fields
- \(\epsilon\)-nets and simplex range queries
- Efficient partition trees
- New applications of random sampling in computational geometry
- The complexity of the word problems for commutative semigroups and polynomial ideals
- Distinct distance estimates and low degree polynomial partitioning
- A semi-algebraic version of Zarankiewicz's problem
- On a real analog of Bezout inequality and the number of connected components of sign conditions
- Unit Distances in Three Dimensions
- The Structure of Polynomial Ideals and Gröbner Bases
- A First Course in Computational Algebraic Geometry
- Improved bounds for incidences between points and circles
- Space-efficient Gröbner basis computation without degree bounds
- Curve-Sensitive Cuttings
- Incidences between points and lines in three dimensions
- On Range Searching with Semialgebraic Sets. II
- An improved bound on the number of point-surface incidences in three dimensions
- Algorithms in real algebraic geometry
- Polynomial partitioning on varieties of codimension two and point-hypersurface incidences in four dimensions
