Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications

DOI10.1137/19M1268550MaRDI QIDQ4989918

Esther Ezra, Joshua Zahl, Pankaj K. Agarwal, Boris Aronov

Publication date: 27 May 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

quantifier eliminationpolynomial partitioning\(\epsilon\)-samplessemialgebraic range spaces

Mathematics Subject Classification ID

Effectivity, complexity and computational aspects of algebraic geometry (14Q20) General topics in the theory of algorithms (68W01) General topics in the theory of computing (68Q01)

Related Items

On Ray Shooting for Triangles in 3-Space and Related Problems, On reverse shortest paths in geometric proximity graphs, Throwing a sofa through the window, On semialgebraic range reporting, Few cuts meet many point sets, On the Stretch Factor of Polygonal Chains, 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, On 3SUM-hard problems in the decision tree model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Refined bounds on the number of connected components of sign conditions on a variety
• An incidence theorem in higher dimensions
• On the Erdős distinct distances problem in the plane
• On range searching with semialgebraic sets
• Almost tight bounds for eliminating depth cycles in three dimensions
• Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
• Multilevel polynomial partitions and simplified range searching
• Cutting algebraic curves into pseudo-segments and applications
• A semi-algebraic version of Zarankiewicz's problem
• Almost tight upper bounds for vertical decompositions in four dimensions
• Eliminating Depth Cycles among Triangles in Three Dimensions
• Algorithms in Real Algebraic Geometry: A Survey
• Simplex Range Searching and Its Variants: A Review
• New bounds on curve tangencies and orthogonalities
• Constructive Polynomial Partitioning for Algebraic Curves in ℝ³ with Applications
• Pseudo-Line Arrangements: Duality, Algorithms, and Applications
• Polynomial partitioning for a set of varieties
• On Range Searching with Semialgebraic Sets. II
• Lower Bounds for Approximation by Nonlinear Manifolds
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Algorithms in real algebraic geometry