Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

Lower bounds on the complexity of polytope range searching


Author: Bernard Chazelle
Journal: J. Amer. Math. Soc. 2 (1989), 637-666
MSC: Primary 68Q25; Secondary 68P05, 68P10, 68U05
DOI: https://doi.org/10.1090/S0894-0347-1989-1001852-0
MathSciNet review: 1001852
Full-text PDF Free Access

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • [1] M. Abramowitz and I. A. Stegun, Handbook of mathematical functions, Dover, New York, 1970.
  • [2] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, MA, 1974. MR 0413592 (54:1706)
  • [3] W. A. Burkhard, M. L. Fredman, and D. J. Kleitman, Inherent complexity trade-offs for range query problems, Theor. Comput. Sci. 16 (1981), 279-290. MR 642322 (83h:68055)
  • [4] B. Chazelle, Lower bounds on the complexity of multidimensional searching, Proc. 27th Annual IEEE Sympos. on Foundations of Computer Science, IEEE, New York, 1986, pp. 87-96.
  • [5] B. Chazelle and E. Welzl, Quasi-optimal range searching in spaces of finite $ VC$-dimension, Discrete Comput. Geom. 4 (5) (1988). MR 1014739 (91d:68122)
  • [6] R. Cole and C. K. Yap, Geometric retrieval problems, Inform. and Control 63 (1984), 39-57. MR 837077 (87j:68045)
  • [7] H. Edelsbrunner and E. Welzl, Halfplanar range search in linear space and $ O({n^{0.695}})$ query time, Inform. Process. Lett. 23 (1986), 289-293.
  • [8] P. Erdös and J. Spencer, Probabilistic methods in combinatorics, Academic Press, New York, 1974. MR 0382007 (52:2895)
  • [9] M. L. Fredman, A lower bound on the complexity of orthogonal range queries, J. Assoc. Comput. Mach. 28 (1981), 696-705. MR 677081 (83k:68012)
  • [10] -, Lower bounds on the complexity of some optimal data structures, SIAM J. Comput. 10 (1981), 1-10. MR 605599 (83b:68072)
  • [11] D. Haussler and E. Welzl, Epsilon-nets and simplex range queries, Discrete Comput. Geom. 2 (1987), 127-151. MR 884223 (88d:68099)
  • [12] J. Komlós, E. Szemerédi, and J. Pintz, On Heilbronn's triangle problem, J. London Math. Soc. (2) 24 (1981), 385-396.
  • [13] -, A lower bound for Heilbronn's problem, J. London Math. Soc. (2) 25 (1982), 13-24. MR 645860 (83i:10042)
  • [14] A. M. Macbeath, A compactness theorem for affine equivalence classes of convex regions, Canad. J. Math. 3 (1951), 54-61. MR 0045406 (13:577f)
  • [15] K. Mehlhorn, Data structures and algorithms 3: Multidimensional searching and computational geometry, Springer-Verlag, Berlin and New York, 1984. MR 756415 (86e:68003)
  • [16] W. O. J. Moser, Problems on extremal properties of a finite set of points, Discrete Geometry and Convexity, Ann. New York Acad. Sci. 440 (1985), 52-64. MR 809191 (87g:52003)
  • [17] L. A. Santaló, Integral geometry and geometric probability, Encyclopaedia Math. Appl. Vol. 1 (Gian-Carlo Rota, ed.), Addison-Wesley, Reading, MA, 1976. MR 0433364 (55:6340)
  • [18] D. E. Willard, Polygon retrieval, SIAM J. Comput. 11 (1982), 149-165. MR 646770 (83f:68030)
  • [19] A. C. Yao, On the complexity of maintaining partial sums, SIAM J. Comput. 14 (1985), 277-288. MR 784737 (86i:68053)
  • [20] F. F. Yao, A $ 3$-space partition and its applications, Proc. 15th Annual ACM Sympos. on Theory of Comput., ACM, New York, 1983, pp. 258-263.
  • [21] A. C. Yao and F. F. Yao, On computing the rank function for a set of vectors, Report No. UIUCDCS-R-75-699, Univ. of Illinois at Urbana-Champaign, 1975.
  • [22] -, A general approach to $ d$-dimensional geometric queries, Proc. 17th Annual ACM Sympos. on Theory of Comput., ACM, New York, 1985, pp. 163-168.

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC: 68Q25, 68P05, 68P10, 68U05

Retrieve articles in all journals with MSC: 68Q25, 68P05, 68P10, 68U05


Additional Information

DOI: https://doi.org/10.1090/S0894-0347-1989-1001852-0
Article copyright: © Copyright 1989 American Mathematical Society

American Mathematical Society