Geodesic
Lower bounds on the complexity of polytope range searching
Journal of the American Mathematical Society, Tome 02 (1989) no. 4, pp. 637-666

Voir la notice de l'article provenant de la source American Mathematical Society

@article{10_1090_S0894_0347_1989_1001852_0,
     author = {Chazelle, Bernard},
     title = {Lower bounds on the complexity of polytope range searching},
     journal = {Journal of the American Mathematical Society},
     pages = {637--666},
     publisher = {mathdoc},
     volume = {02},
     number = {4},
     year = {1989},
     doi = {10.1090/S0894-0347-1989-1001852-0},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1989-1001852-0/}
}
TY  - JOUR
AU  - Chazelle, Bernard
TI  - Lower bounds on the complexity of polytope range searching
JO  - Journal of the American Mathematical Society
PY  - 1989
SP  - 637
EP  - 666
VL  - 02
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1989-1001852-0/
DO  - 10.1090/S0894-0347-1989-1001852-0
ID  - 10_1090_S0894_0347_1989_1001852_0
ER  - 
%0 Journal Article
%A Chazelle, Bernard
%T Lower bounds on the complexity of polytope range searching
%J Journal of the American Mathematical Society
%D 1989
%P 637-666
%V 02
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1989-1001852-0/
%R 10.1090/S0894-0347-1989-1001852-0
%F 10_1090_S0894_0347_1989_1001852_0
Chazelle, Bernard. Lower bounds on the complexity of polytope range searching. Journal of the American Mathematical Society, Tome 02 (1989) no. 4, pp. 637-666. doi: 10.1090/S0894-0347-1989-1001852-0

[1] Aho, Alfred V., Hopcroft, John E., Ullman, Jeffrey D. The design and analysis of computer algorithms 1975

[2] Burkhard, Walter A., Fredman, Michael L., Kleitman, Daniel J. Inherent complexity trade-offs for range query problems Theoret. Comput. Sci. 1981 279 290

[3] Chazelle, Bernard, Welzl, Emo Quasi-optimal range searching in spaces of finite VC-dimension Discrete Comput. Geom. 1989 467 489

[4] Cole, Richard, Yap, Chee-K. Geometric retrieval problems Inform. and Control 1984 39 57

[5] Erdå‘S, Paul, Spencer, Joel Probabilistic methods in combinatorics 1974 106

[6] Fredman, Michael L. A lower bound on the complexity of orthogonal range queries J. Assoc. Comput. Mach. 1981 696 705

[7] Fredman, Michael L. Lower bounds on the complexity of some optimal data structures SIAM J. Comput. 1981 1 10

[8] Haussler, David, Welzl, Emo 𝜀-nets and simplex range queries Discrete Comput. Geom. 1987 127 151

[9] Komlã³S, Jã¡Nos, Pintz, Jã¡Nos, Szemerã©Di, Endre A lower bound for Heilbronn’s problem J. London Math. Soc. (2) 1982 13 24

[10] Macbeath, A. M. A compactness theorem for affine equivalence-classes of convex regions Canad. J. Math. 1951 54 61

[11] Mehlhorn, Kurt Data structures and algorithms. 3 1984

[12] Moser, W. O. J. Problems on extremal properties of a finite set of points 1985 52 64

[13] Santalã³, Luis A. Integral geometry and geometric probability 1976

[14] Willard, Dan E. Polygon retrieval SIAM J. Comput. 1982 149 165

[15] Yao, Andrew C. On the complexity of maintaining partial sums SIAM J. Comput. 1985 277 288

Cité par Sources :