The power of nonmonotonicity in geometric searching

Bernard Chazelle

doi:10.1145/513400.513411

The power of nonmonotonicity in geometric searching

Research output: Contribution to conference › Paper › 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	88-93
Number of pages	6
DOIs	https://doi.org/10.1145/513400.513411
State	Published - 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/Territory	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

Access to Document

10.1145/513400.513411

Cite this

@conference{c2e36f29cb5b47ba89cb9a0e6165f3be,

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 Θ(n1+c) arithmetic operations, for some constant c>0.",

keywords = "Circuit Complexity, Fourier Transform, Range Searching, Spectral Bounds",

author = "Bernard Chazelle",

year = "2002",

doi = "10.1145/513400.513411",

language = "English (US)",

pages = "88--93",

note = "Proceedings of the 18th Annual Symposium on Computational Geometry (SCG'02) ; Conference date: 05-06-2002 Through 07-06-2002",

}

TY - CONF

T1 - The power of nonmonotonicity in geometric searching

AU - Chazelle, Bernard

PY - 2002

Y1 - 2002

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

KW - Circuit Complexity

KW - Fourier Transform

KW - Range Searching

KW - Spectral Bounds

UR - http://www.scopus.com/inward/record.url?scp=0036362538&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036362538&partnerID=8YFLogxK

U2 - 10.1145/513400.513411

DO - 10.1145/513400.513411

M3 - Paper

AN - SCOPUS:0036362538

SP - 88

EP - 93

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

Y2 - 5 June 2002 through 7 June 2002

ER -

The power of nonmonotonicity in geometric searching

Abstract

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this