The Power of Nonmonotonicity in Geometric Searching

Research output: Contribution to journalArticlepeer-review

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 Ω(n 1+c) arithmetic operations, for some constant c > 0.

Original languageEnglish (US)
Pages (from-to)3-16
Number of pages14
JournalDiscrete and Computational Geometry
Volume31
Issue number1
DOIs
StatePublished - Jan 1 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'The Power of Nonmonotonicity in Geometric Searching'. Together they form a unique fingerprint.

Cite this