Multilevel polynomial partitions and simplified range searching

DOI10.1007/S00454-015-9701-2MaRDI QIDQ2354673zbMATH OpenOpenAlexFDO

Authors Jiří Matoušek, Zuzana Safernova

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

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: The polynomial partitioning method of Guth and Katz [arXiv:1011.4105] has numerous applications in discrete and computational geometry. It partitions a given $n$-point set $Psubsetmathbb{R}^d$ using the zero set $Z(f)$ of a suitable $d$-variate polynomial $f$. Applications of this result are often complicated by the problem, what should be done with the points of $P$ lying within $Z(f)$? A natural approach is to partition these points with another polynomial and continue further in a similar manner. So far it has been pursued with limited success---several authors managed to construct and apply a second partitioning polynomial, but further progress has been prevented by technical obstacles. We provide a polynomial partitioning method with up to $d$ polynomials in dimension $d$, which allows for a complete decomposition of the given point set. We apply it to obtain a new algorithm for the semialgebraic range searching problem. Our algorithm has running time bounds similar to a recent algorithm by Agarwal, Sharir, and the first author [SIAM~J.~Comput. 42(2013) 2039--2062], but it is simpler both conceptually and technically. While this paper has been in preparation, Basu and Sombra, as well as Fox, Pach, Sheffer, Suk, and Zahl, obtained results concerning polynomial partitions which overlap with ours to some extent.

Recommendations

• An efficient algorithm for generalized polynomial partitioning and its applications
• Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
• Polynomial partitioning for several sets of varieties
• ON MULTI-LEVEL k-RANGES FOR RANGE SEARCH
• scientific article; zbMATH DE number 1594561
• An approximating polynomial algorithm for a sequence partitioning problem
• Partitioning procedure for polynomial optimization
• Polynomial partitioning for a set of varieties
• Lower Bounds on the Complexity of Polytope Range Searching
• A Polynomial Time Algorithm for Shaped Partition Problems

Cites work

• -nets and simplex range queries
• A First Course in Computational Algebraic Geometry
• A semi-algebraic version of Zarankiewicz's problem
• A Szemerédi-Trotter type theorem in R^4
• Algorithms in real algebraic geometry
• An improved bound on the number of point-surface incidences in three dimensions
• An incidence theorem in higher dimensions
• Curve-Sensitive Cuttings
• Definability and fast quantifier elimination in algebraically closed fields
• Distinct distance estimates and low degree polynomial partitioning
• Efficient partition trees
• Elementary structure of real algebraic varieties
• scientific article; zbMATH DE number 52497 (Why is no real title available?)
• scientific article; zbMATH DE number 3572315 (Why is no real title available?)
• scientific article; zbMATH DE number 1201576 (Why is no real title available?)
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 1254276 (Why is no real title available?)
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Improved bounds for incidences between points and circles
• Incidences between points and lines in three dimensions
• Integral closure of ideals, rings, and modules
• New applications of random sampling in computational geometry
• On a real analog of Bézout inequality and the number of connected components of sign conditions
• On range searching with semialgebraic sets. II.
• On the Erdős distinct distances problem in the plane
• Optimal partition trees
• Polynomial partitioning on varieties of codimension two and point-hypersurface incidences in four dimensions
• Refined bounds on the number of connected components of sign conditions on a variety
• Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique
• Space-efficient Gröbner basis computation without degree bounds
• The complexity of the word problems for commutative semigroups and polynomial ideals
• The Structure of Polynomial Ideals and Gröbner Bases
• Unit distances in three dimensions

Cited in

(36)

• Polynomial partitioning for several sets of varieties
• 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
• \(L^2\) bounds for a maximal directional Hilbert transform
• The polynomial method over varieties
• Cutting algebraic curves into pseudo-segments and applications
• Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
• A semi-algebraic version of Zarankiewicz's problem
• Few cuts meet many point sets
• On a real analog of Bézout inequality and the number of connected components of sign conditions
• Simplex Range Searching and Its Variants: A Review
• Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
• On the stretch factor of polygonal chains
• Maximal directional operators along algebraic varieties
• 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
• Constructive polynomial partitioning for algebraic curves in \(\mathbb{R}^3\) with applications
• On range searching with semialgebraic sets. II.
• Polynomial partitioning on varieties of codimension two and point-hypersurface incidences in four dimensions
• On reverse shortest paths in geometric proximity graphs
• Throwing a sofa through the window
• On semialgebraic range reporting
• Partitioning theorems for sets of semi-Pfaffian sets, with applications
• 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
• Improved algebraic degeneracy testing
• Intersection searching amid tetrahedra in 4-space and efficient continuous collision detection
• Intersection searching amid tetrahedra in four dimensions
• Lower bounds for semialgebraic range searching and stabbing problems
• Lower bounds for semialgebraic range searching and stabbing problems
• Semi-algebraic off-line range searching and biclique partitions in the plane
• Sparse bounded hop-spanners for geometric intersection graphs
• Compact representation of semilinear and terrain-like graphs

This page was built for publication: Multilevel polynomial partitions and simplified range searching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354673)