On Range Searching in the Group Model and Combinatorial Discrepancy

DOI10.1137/120865240zbMath1297.68065OpenAlexW2127125853MaRDI QIDQ5494934

Kasper Green Larsen

Publication date: 30 July 2014

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

Full work available at URL: https://doi.org/10.1137/120865240

zbMATH Keywords

discrepancylower boundscomputational geometryrange searchinggroup model

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Related Items (8)

Polynomial Data Structure Lower Bounds in the Group Model ⋮ Simplex Range Searching and Its Variants: A Review ⋮ TIGHTER BOUNDS FOR THE DISCREPANCY OF BOXES AND POLYTOPES ⋮ Semi-group range sum revisited: query-space lower bound tightened ⋮ Unnamed Item ⋮ Lower bounds for matrix factorization ⋮ The Communication Complexity of Distributed epsilon-Approximations ⋮ Lower bounds for matrix factorization

This page was built for publication: On Range Searching in the Group Model and Combinatorial Discrepancy