Lower bounds on the complexity of polytope range searching
HTML articles powered by AMS MathViewer
- by Bernard Chazelle
- J. Amer. Math. Soc. 2 (1989), 637-666
- DOI: https://doi.org/10.1090/S0894-0347-1989-1001852-0
- PDF | Request permission
References
- M. Abramowitz and I. A. Stegun, Handbook of mathematical functions, Dover, New York, 1970.
- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR 0413592
- Walter A. Burkhard, Michael L. Fredman, and Daniel J. Kleitman, Inherent complexity trade-offs for range query problems, Theoret. Comput. Sci. 16 (1981), no. 3, 279–290. MR 642322, DOI 10.1016/0304-3975(81)90099-2 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.
- Bernard Chazelle and Emo Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, Discrete Comput. Geom. 4 (1989), no. 5, 467–489. MR 1014739, DOI 10.1007/BF02187743
- Richard Cole and Chee-K. Yap, Geometric retrieval problems, Inform. and Control 63 (1984), no. 1-2, 39–57. MR 837077, DOI 10.1016/S0019-9958(84)80040-6 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.
- Paul Erdős and Joel Spencer, Probabilistic methods in combinatorics, Probability and Mathematical Statistics, Vol. 17, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1974. MR 0382007
- Michael L. Fredman, A lower bound on the complexity of orthogonal range queries, J. Assoc. Comput. Mach. 28 (1981), no. 4, 696–705. MR 677081, DOI 10.1145/322276.322281
- Michael L. Fredman, Lower bounds on the complexity of some optimal data structures, SIAM J. Comput. 10 (1981), no. 1, 1–10. MR 605599, DOI 10.1137/0210001
- David Haussler and Emo Welzl, $\epsilon$-nets and simplex range queries, Discrete Comput. Geom. 2 (1987), no. 2, 127–151. MR 884223, DOI 10.1007/BF02187876 J. Komlós, E. Szemerédi, and J. Pintz, On Heilbronn’s triangle problem, J. London Math. Soc. (2) 24 (1981), 385-396.
- János Komlós, János Pintz, and Endre Szemerédi, A lower bound for Heilbronn’s problem, J. London Math. Soc. (2) 25 (1982), no. 1, 13–24. MR 645860, DOI 10.1112/jlms/s2-25.1.13
- A. M. Macbeath, A compactness theorem for affine equivalence-classes of convex regions, Canad. J. Math. 3 (1951), 54–61. MR 45406, DOI 10.4153/cjm-1951-008-7
- Kurt Mehlhorn, Data structures and algorithms. 3, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin, 1984. Multidimensional searching and computational geometry. MR 756415, DOI 10.1007/978-3-642-69900-9
- W. O. J. Moser, Problems on extremal properties of a finite set of points, Discrete geometry and convexity (New York, 1982) Ann. New York Acad. Sci., vol. 440, New York Acad. Sci., New York, 1985, pp. 52–64. MR 809191, DOI 10.1111/j.1749-6632.1985.tb14538.x
- Luis A. Santaló, Integral geometry and geometric probability, Encyclopedia of Mathematics and its Applications, Vol. 1, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. With a foreword by Mark Kac. MR 0433364
- Dan E. Willard, Polygon retrieval, SIAM J. Comput. 11 (1982), no. 1, 149–165. MR 646770, DOI 10.1137/0211012
- Andrew C. Yao, On the complexity of maintaining partial sums, SIAM J. Comput. 14 (1985), no. 2, 277–288. MR 784737, DOI 10.1137/0214022 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. 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. —, A general approach to $d$-dimensional geometric queries, Proc. 17th Annual ACM Sympos. on Theory of Comput., ACM, New York, 1985, pp. 163-168.
Bibliographic Information
- © Copyright 1989 American Mathematical Society
- 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