We establish a nonlinear lower bound for halfplane range searching over a group. Specifically, we show that summing up the weights of n (weighted) points within n halfplanes requires Ω(n log n) additions and subtractions. This is the first nontrivial lower bound for range searching over a group. By contrast, range searching over a semigroup (which forbids subtractions) is almost completely understood. Our proof has two parts. First, we develop a general, entropy-based method for relating the linear circuit complexity of a linear map A to the spectrum of Atop;A. In the second part of the proof, we design a "high-spectrum" geometric set system for halfplane range searching and, using techniques from discrepancy theory, we estimate the median eigenvalue of its associated map. Interestingly, the method also shows that using up to a linear number of help gates cannot help; these are gates that can compute any bivariate function.
All Science Journal Classification (ASJC) codes
- Computer Science(all)
- Circuit complexity
- Lower bounds
- Range searching