A spectral approach to lower bounds with applications to geometric searching

Research output: Contribution to journalArticle

15 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)545-556
Number of pages12
JournalSIAM Journal on Computing
Volume27
Issue number2
DOIs
StatePublished - Jan 1 1998

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Circuit complexity
  • Eigenvalues
  • Lower bounds
  • Range searching

Fingerprint Dive into the research topics of 'A spectral approach to lower bounds with applications to geometric searching'. Together they form a unique fingerprint.

  • Cite this