The power of nonmonotonicity in geometric searching

Research output: Contribution to conferencePaper

Abstract

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)
Pages88-93
Number of pages6
DOIs
StatePublished - Jan 1 2002
EventProceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) - Barcelona, Spain
Duration: Jun 5 2002Jun 7 2002

Other

OtherProceedings of the 18th Annual Symposium on Computational Geometry (SCG'02)
CountrySpain
CityBarcelona
Period6/5/026/7/02

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Keywords

  • 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

    Chazelle, B. (2002). The power of nonmonotonicity in geometric searching. 88-93. Paper presented at Proceedings of the 18th Annual Symposium on Computational Geometry (SCG'02), Barcelona, Spain. https://doi.org/10.1145/513400.513411