Lower bounds for orthogonal range searching: part II. The arithmetic model

DOI10.1145/79147.79149zbMath0699.68058OpenAlexW2038521122MaRDI QIDQ3477952

Bernard Chazelle

Publication date: 1990

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/79147.79149

zbMATH Keywords

data structuresorthogonal range searchingLower boundsdominance search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Related Items

An efficient \(k\) nearest neighbors searching algorithm for a query line., Lower bounds for off-line range searching, Can visibility graphs be represented compactly?, On the difficulty of range searching, Polynomial Data Structure Lower Bounds in the Group Model, The range 1 query (R1Q) problem, Approximate covering detection among content-based subscriptions using space filling curves, Dynamic orthogonal range queries in OLAP., On semialgebraic range reporting, Tight lower bounds for halfspace range searching, Simplex Range Searching and Its Variants: A Review, Space efficient dynamic orthogonal range reporting, Semi-group range sum revisited: query-space lower bound tightened, How hard is half-space range searching?, On the difficulty of range searching., OPTIMAL RANGE MAX DATACUBE FOR FIXED DIMENSIONS, A new framework for addressing temporal range queries and some preliminary results, Approximate range searching: The absolute model, On the minimum total length of interval systems expressing all intervals, and range-restricted queries, A New Lower Bound for Semigroup Orthogonal Range Searching