The Power of Nonmonotonicity in Geometric Searching

Bernard Chazelle

doi:10.1007/s00454-003-2946-1

The Power of Nonmonotonicity in Geometric Searching

Bernard Chazelle

Research output: Contribution to journal › Article › peer-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 Θ(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 (from-to)	3-16
Number of pages	14
Journal	Discrete and Computational Geometry
Volume	31
Issue number	1
DOIs	https://doi.org/10.1007/s00454-003-2946-1
State	Published - Jan 2004
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1007/s00454-003-2946-1

Cite this

@article{d6e57b3700ca4840b284c1ca029a3fca,

title = "The Power of Nonmonotonicity in Geometric Searching",

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.",

author = "Bernard Chazelle",

year = "2004",

month = jan,

doi = "10.1007/s00454-003-2946-1",

language = "English (US)",

volume = "31",

pages = "3--16",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - The Power of Nonmonotonicity in Geometric Searching

AU - Chazelle, Bernard

PY - 2004/1

Y1 - 2004/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/1142276426

UR - https://www.scopus.com/pages/publications/1142276426#tab=citedBy

U2 - 10.1007/s00454-003-2946-1

DO - 10.1007/s00454-003-2946-1

M3 - Article

AN - SCOPUS:1142276426

SN - 0179-5376

VL - 31

SP - 3

EP - 16

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

The Power of Nonmonotonicity in Geometric Searching

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this