### 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 Θ(n^{3/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 language | English (US) |
---|---|

Pages | 88-93 |

Number of pages | 6 |

DOIs | |

State | Published - Jan 1 2002 |

Event | Proceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) - Barcelona, Spain Duration: Jun 5 2002 → Jun 7 2002 |

### Other

Other | Proceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) |
---|---|

Country | Spain |

City | Barcelona |

Period | 6/5/02 → 6/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