On range searching with semialgebraic sets. II.
From MaRDI portal
Abstract: Let be a set of points in . We present a linear-size data structure for answering range queries on with constant-complexity semialgebraic sets as ranges, in time close to . It essentially matches the performance of similar structures for simplex range searching, and, for , significantly improves earlier solutions by the first two authors obtained in~1994. This almost settles a long-standing open problem in range searching. The data structure is based on the polynomial-partitioning technique of Guth and Katz [arXiv:1011.4105], which shows that for a parameter , , there exists a -variate polynomial of degree such that each connected component of contains at most points of , where is the zero set of . We present an efficient randomized algorithm for computing such a polynomial partition, which is of independent interest and is likely to have additional applications.
Recommendations
Cited in
(41)- On range searching with semialgebraic sets
- On separating points by lines
- Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
- On 3SUM-hard problems in the decision tree model
- Dynamic geometric data structures via shallow cuttings
- Multilevel polynomial partitions and simplified range searching
- Four Soviets walk the dog: improved bounds for computing the Fréchet distance
- Straight-path queries in trajectory data
- Few cuts meet many point sets
- On the Zarankiewicz problem for intersection hypergraphs
- On a real analog of Bézout inequality and the number of connected components of sign conditions
- Semialgebraic Range Reporting and Emptiness Searching with Applications
- Simplex Range Searching and Its Variants: A Review
- Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
- On the stretch factor of polygonal chains
- Polynomial data structure lower bounds in the group model
- An efficient algorithm for generalized polynomial partitioning and its applications
- On the stretch factor of polygonal chains
- On range searching with semialgebraic sets
- Constructive polynomial partitioning for algebraic curves in \(\mathbb{R}^3\) with applications
- Representation complexities of semialgebraic graphs
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- Polynomial partitioning for a set of varieties
- Improved bounds for incidences between points and circles
- Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
- On reverse shortest paths in geometric proximity graphs
- Dynamic data structures for \(k\)-nearest neighbor queries
- On semialgebraic range reporting
- An optimal sparsification lemma for low-crossing matchings and its applications to discrepancy and approximations
- Semialgebraic range stabbing, ray shooting, and intersection counting in the plane
- Semi-algebraic off-line range searching and biclique partitions in the plane
- Intersection queries for flat semi-algebraic objects in three dimensions and related problems
- Chromatic k-nearest neighbor queries
- Intersection searching amid tetrahedra in 4-space and efficient continuous collision detection
- Intersection searching amid tetrahedra in four dimensions
- Line intersection searching amid unit balls in 3-space
- Lower bounds for semialgebraic range searching and stabbing problems
- Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
- Lower bounds for semialgebraic range searching and stabbing problems
- Escaping the curse of spatial partitioning: matchings with low crossing numbers and their applications
- Semi-algebraic off-line range searching and biclique partitions in the plane
This page was built for publication: On range searching with semialgebraic sets. II.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5408758)