The power of nonmonotonicity in geometric searching

ABSTRACT

(MATH) We define a close variant of line range searching over the reals and prove that its arithmetic complexity is $\Theta(n log n) if field operations are allowed and $\Theta(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 &OHgr;(n ^1+c) arithmetic operations, for some constant c>0.

REFERENCES

• 1: Agarwal, P.K., Erickson, J. Geometric range searching and its relatives, in "Advances in Discrete and Computational Geometry," eds. Chazelle, B., Goodman, J.E., Pollack, R., Contemporary Mathematics 223, Amer. Math. Soc., 1999, pp. 1--56.
• 2: Artin, M. Algebra, Prentice Hall, 1991.
• 3: Baum, U., Clausen, M., Tietz, B. Improved upper complexity bounds for the discrete Fourier transform, Applicable Algebra in Engineering, Communication and Computing 2 (1991), 35--43.
• 4: Bernard Chazelle, A Spectral Approach to Lower Bounds with Applications to Geometric Searching, SIAM Journal on Computing, v.27 n.2, p.545-556, April 1998 [doi>10.1137/S0097539794275665]
• 5: Chazelle, B. Lower bounds for off-line range searching, Disc. Comput. Geom. 17 (1997), 53--65.
• 6: Chazelle, B., Lvov, A. A trace bound for the hereditary discrepancy, Disc. Comput. Geom. 26 (2001), 221--231.
• 7: Bernard Chazelle, The discrepancy method: randomness and complexity, Cambridge University Press, New York, NY, 2000
• 8: M. Clausen, Fast Fourier transforms for metabelian groups, SIAM Journal on Computing, v.18 n.3, p.584-593, June 1989 [doi>10.1137/0218040]
• 9: Hardy, G.H., Wright, E.M. An Introduction to the Theory of Numbers, 5th ed., Oxford Science Publications, 1979.
• 10: Maslen, D.K., Rockmore, D.N. Generalized FFTS - A survey of some recent results, in "Groups and Computation II", eds. L. Finkelstein and W.M. Kantor, DIMACS Series in Disc. Math. and Theoret. Comput. Sci. 28 (1997), 183--237.
• 11: Matoušek, J. Range searching with efficient hierarchical cuttings, Disc. Comput. Geom. 10 (1993), 157--182.
• 12: Jiří Matoušek, Geometric range searching, ACM Computing Surveys (CSUR), v.26 n.4, p.422-461, Dec. 1994 [doi>10.1145/197405.197408]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
circuit complexity, fourier transform, range searching, spectral bounds