{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:00:33Z","timestamp":1787385633013,"version":"3.56.0"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,1,1]],"date-time":"1997-01-01T00:00:00Z","timestamp":852076800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1997,1]]},"DOI":"10.1007\/bf02770864","type":"journal-article","created":{"date-parts":[[2007,12,14]],"date-time":"2007-12-14T04:05:40Z","timestamp":1197605140000},"page":"53-65","source":"Crossref","is-referenced-by-count":13,"title":["Lower bounds for off-line range searching"],"prefix":"10.1007","volume":"17","author":[{"given":"B.","family":"Chazelle","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF02770864_CR1","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J.The Probabilistic Method, Wiley, New York, 1992."},{"key":"BF02770864_CR2","series-title":"Cambridge Tracts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511565984","volume-title":"Irregularities of Distribution","author":"J. Beck","year":"1987","unstructured":"Beck, J., Chen, W. W. L.Irregularities of Distribution, Cambridge Tracts in Mathematics, vol. 89, Cambridge University Press, Cambridge, 1987."},{"key":"BF02770864_CR3","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1090\/S0894-0347-1989-1001852-0","volume":"2","author":"B. Chazelle","year":"1989","unstructured":"Chazelle, B. Lower bounds on the complexity of polytope range searching,J. Amer. Math. Soc,2 (1989), 637\u2013666.","journal-title":"J. Amer. Math. Soc"},{"key":"BF02770864_CR4","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1145\/79147.79149","volume":"37","author":"B. Chazelle","year":"1990","unstructured":"Chazelle, B. Lower bounds for orthogonal range searching: II. The arithmetic model,J. Assoc. Comput. Mach.,37 (1990), 439\u2013463.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02770864_CR5","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1142\/9789812831699_0002","volume-title":"Computing in Euclidean Geometry","author":"B. Chazelle","year":"1995","unstructured":"Chazelle, B. Computational geometry: A retrospective, in:Computing in Euclidean Geometry, 2nd edn., eds. D.-Z. Du and F. Hwang, World Scientific Press, Singapore, 1995, pp. 22\u201346.","edition":"2nd"},{"key":"BF02770864_CR6","unstructured":"Chazelle, B. A spectral approach to lower bounds with applications to geometric searching,SIAM J. Comput. (1996), to appear."},{"key":"BF02770864_CR7","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0925-7721(95)00002-X","volume":"5","author":"B. Chazelle","year":"1996","unstructured":"Chazelle, B., Rosenberg, B. Lower bounds on the complexity of simplex range reporting on a pointer machine,Comput. Geom. Theory Appl. 5 (1996), 237\u2013247. Preliminary version inProc. 19th ICALP, LNCS 623, Springer-Verlag, Berlin, 1992, pp. 439\u2013449.","journal-title":"Comput. Geom. Theory Appl."},{"key":"BF02770864_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"Edelsbrunner, H.Algorithms in Combinatorial Geometry, Springer-Verlag, New York, 1987."},{"key":"BF02770864_CR9","doi-asserted-by":"crossref","unstructured":"Erickson, J. New lower bounds for Hopcroft\u2019s problem,Proc. 11thAnn. ACM Symp. on Computational Geometry, 1995, to appear.","DOI":"10.1145\/220279.220293"},{"key":"BF02770864_CR10","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1145\/322276.322281","volume":"28","author":"M. L. Fredman","year":"1981","unstructured":"Fredman, M. L. A lower bound on the complexity of orthogonal range queries,J. Assoc. Comput. Mach.,28 (1981), 696\u2013705.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02770864_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0210001","volume":"10","author":"M. L. Fredman","year":"1981","unstructured":"Fredman, M. L. Lower bounds on the complexity of some optimal data structures,SIAM J. Comput.,10 (1981), 1\u201310.","journal-title":"SIAM J. Comput."},{"key":"BF02770864_CR12","volume-title":"The Theory of Matrices","author":"P. Lancaster","year":"1985","unstructured":"Lancaster, P., Tismenetsky, M.The Theory of Matrices, 2nd edn., Academic Press, New York, 1985.","edition":"2nd"},{"key":"BF02770864_CR13","unstructured":"Matou\u0161ek, J. Geometric range searching, Tech. Report B-93-09, Free University Berlin, 1993."},{"key":"BF02770864_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69900-9","volume-title":"Data Structures and Algorithms 3:Multidimensional Searching and Computational Geometry","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K.Data Structures and Algorithms 3:Multidimensional Searching and Computational Geometry, Springer-Verlag, Heidelberg, 1984."},{"key":"BF02770864_CR15","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1145\/321752.321761","volume":"20","author":"J. Morgenstern","year":"1973","unstructured":"Morgenstern, J. Note on a lower bound of the linear complexity of the fast Fourier transform,J. Assoc. Comput. Mach.,20 (1973), 305\u2013306.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02770864_CR16","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"K. Mulmuley","year":"1994","unstructured":"Mulmuley, K.Computational Geometry: An Introduction Through Randomized Algorithms, Prentice-Hall, Englewood Cliffs, NJ, 1994."},{"key":"BF02770864_CR17","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1112\/S0025579300000541","volume":"1","author":"K. F. Roth","year":"1954","unstructured":"Roth, K. F. On irregularities of distribution,Mathematika,1 (1954), 73\u201339.","journal-title":"Mathematika"},{"key":"BF02770864_CR18","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0214022","volume":"14","author":"A. C. Yao","year":"1985","unstructured":"Yao, A. C. On the complexity of maintaining partial sums,SIAM J. Comput.,14 (1985), 277\u2013288.","journal-title":"SIAM J. Comput."},{"key":"BF02770864_CR19","first-page":"343","volume-title":"Algorithms and Complexity, Handbook of Theoretical Computer Science","author":"F. F. Yao","year":"1990","unstructured":"Yao, F. F. Computational geometry, in:Algorithms and Complexity, Handbook of Theoretical Computer Science, Vol. A, ed. J. van Leeuwen, Elsevier, Amsterdam, 1990, pp. 343\u2013389."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02770864.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02770864\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02770864","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T22:02:36Z","timestamp":1558389756000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02770864"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,1]]}},"alternative-id":["BF02770864"],"URL":"https:\/\/doi.org\/10.1007\/bf02770864","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,1]]}}}