The Power of Nonmonotonicity in Geometric Searching

Research output: Contribution to journalArticlepeer-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 Ω(n 1+c) arithmetic operations, for some constant c > 0.

Original languageAmerican English
Pages (from-to)3-16
Number of pages14
JournalDiscrete and Computational Geometry
Issue number1
StatePublished - Jan 2004

ASJC Scopus subject areas

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

Cite this