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 

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
@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},
     year = {1989},
     volume = {02},
     number = {4},
     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
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
%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

[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 :