On Range Searching with Semialgebraic Sets. II
From MaRDI portal
Publication:5408758
DOI10.1137/120890855zbMath1285.68192arXiv1208.3384OpenAlexW2100503751MaRDI QIDQ5408758
Pankaj K. Agarwal, Micha Sharir, Ji{ří} Matoušek
Publication date: 11 April 2014
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1208.3384
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Semialgebraic sets and related spaces (14P10) Data structures (68P05) Combinatorial complexity of geometric structures (52C45)
Related Items (26)
On the Zarankiewicz problem for intersection hypergraphs ⋮ Straight-path queries in trajectory data ⋮ Polynomial Data Structure Lower Bounds in the Group Model ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance ⋮ On reverse shortest paths in geometric proximity graphs ⋮ Dynamic data structures for \(k\)-nearest neighbor queries ⋮ On semialgebraic range reporting ⋮ Improved Bounds for Incidences Between Points and Circles ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Few cuts meet many point sets ⋮ Dynamic geometric data structures via shallow cuttings ⋮ Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications ⋮ On separating points by lines ⋮ Almost tight bounds for eliminating depth cycles in three dimensions ⋮ Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On a real analog of Bezout inequality and the number of connected components of sign conditions ⋮ Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications ⋮ Representation Complexities of SemiAlgebraic Graphs ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ On the Stretch Factor of Polygonal Chains ⋮ Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions ⋮ Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems ⋮ Multilevel polynomial partitions and simplified range searching ⋮ On 3SUM-hard problems in the decision tree model
This page was built for publication: On Range Searching with Semialgebraic Sets. II
