Semialgebraic Range Reporting and Emptiness Searching with Applications

DOI10.1137/090765092zbMath1228.68058arXiv0908.4061OpenAlexW1855659051MaRDI QIDQ3096093

Hayim Shaul, Micha Sharir

Publication date: 7 November 2011

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

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

zbMATH Keywords

random samplingrange searchingsemialgebraic setsepsilon netsrange reportingray shootingrange emptinesselementary cell partition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Randomized algorithms (68W20)

Related Items (3)

The range 1 query (R1Q) problem ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Near-linear algorithms for geometric hitting sets and set covers

This page was built for publication: Semialgebraic Range Reporting and Emptiness Searching with Applications