The power of nonmonotonicity in geometric searching

Research output: Contribution to conferencePaperpeer-review


We define a close variant of line range searching over the reals and prove that its arithmetic complexity is Θ(n log n) if field operations are allowed and Θ(n3/2) if only additions are. This provides the first nontrivial separation between the monotone and nonmonotone complexity of a range searching problem. The result puts into question the widely held belief that range searching for nonisothetic shapes typically requires Θ(n1+c) arithmetic operations, for some constant c>0.

Original languageEnglish (US)
Number of pages6
StatePublished - Jan 1 2002
EventProceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) - Barcelona, Spain
Duration: Jun 5 2002Jun 7 2002


OtherProceedings of the 18th Annual Symposium on Computational Geometry (SCG'02)

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


  • Circuit Complexity
  • Fourier Transform
  • Range Searching
  • Spectral Bounds

Fingerprint Dive into the research topics of 'The power of nonmonotonicity in geometric searching'. Together they form a unique fingerprint.

Cite this