Journal of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-6834(e) ISSN 0894-0347(p)

Lower bounds on the complexity of polytope range searching

Author(s): Bernard Chazelle
Journal: J. Amer. Math. Soc. 2 (1989), 637-666.
MSC: Primary 68Q25; Secondary 68P05, 68P10, 68U05
MathSciNet review: 1001852
Retrieve article in: PDF
This article is available free of charge

References:

[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 -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 -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 -dimensional geometric queries, Proc. 17th Annual ACM Sympos. on Theory of Comput., ACM, New York, 1985, pp. 163-168.

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|