{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T19:36:07Z","timestamp":1703187367030},"reference-count":37,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1989,7,1]],"date-time":"1989-07-01T00:00:00Z","timestamp":615254400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":8782,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[1989,7]]},"DOI":"10.1016\/0890-5401(89)90064-3","type":"journal-article","created":{"date-parts":[[2004,12,1]],"date-time":"2004-12-01T19:24:20Z","timestamp":1101929060000},"page":"45-64","source":"Crossref","is-referenced-by-count":5,"title":["Lower bounds for the addition-subtraction operations in orthogonal range queries and related problems"],"prefix":"10.1016","volume":"82","author":[{"given":"Dan E.","family":"Willard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0890-5401(89)90064-3_BIB1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","article-title":"Multidimensional binary tree used for associative searching","volume":"18","author":"Bentley","year":"1975","journal-title":"Comm. ACM"},{"key":"10.1016\/0890-5401(89)90064-3_BIB2","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/358841.358850","article-title":"Multidimensional divide-and-conquer","volume":"23","author":"Bentley","year":"1980","journal-title":"Comm ACM"},{"key":"10.1016\/0890-5401(89)90064-3_BIB3","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF00263991","article-title":"Efficient worst-case data structures for range searching","volume":"13","author":"Bentley","year":"1980","journal-title":"Acta Inform."},{"key":"10.1016\/0890-5401(89)90064-3_BIB4","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","article-title":"Decomposable searching problems #1: Static to dynamic transformations","volume":"1","author":"Bentley","year":"1980","journal-title":"J. Algorithms"},{"key":"10.1016\/0890-5401(89)90064-3_BIB5","series-title":"15th Allerton Conf. on Comm., Contr., and Comp.","first-page":"193","article-title":"A problem in multi-variate statistics: Algorthm, data structure and applications","author":"Bentley","year":"1977"},{"key":"10.1016\/0890-5401(89)90064-3_BIB6","series-title":"24th IEEE Symp. on Foundations of Computer Science","first-page":"122","article-title":"Filter search a new approach to query processing","author":"Chazelle","year":"1983"},{"key":"10.1016\/0890-5401(89)90064-3_BIB7","series-title":"25th IEEE Symp. on Foundations of Computer Science","first-page":"165","article-title":"Slimming down data structures a functional approach to algorithm design","author":"Chazelle","year":"1985"},{"key":"10.1016\/0890-5401(89)90064-3_BIB8","series-title":"A functional approach to data structures and its use in multidimensional searching","author":"Chazelle","year":"1985"},{"key":"10.1016\/0890-5401(89)90064-3_BIB9","series-title":"12th ICALP","first-page":"90","article-title":"Fractional cascading: A data structure technique with geometric applications","author":"Chazelle","year":"1985"},{"key":"10.1016\/0890-5401(89)90064-3_BIB10","first-page":"34","article-title":"A note on dynamic range searching","volume":"15","author":"Edelsbrunner","year":"1981","journal-title":"Bull. EATCS"},{"key":"10.1016\/0890-5401(89)90064-3_BIB11","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1016\/0020-0190(82)90068-0","article-title":"On the equivalence of some rectangle search problems","volume":"14","author":"Edelsbrunner","year":"1981","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0890-5401(89)90064-3_BIB12","article-title":"Halfplanar range search in linear space and O(N0.695) time","author":"Edelsbrunner","year":"1983","journal-title":"University of Graz Report F111"},{"key":"10.1016\/0890-5401(89)90064-3_BIB13","series-title":"21st FOCS","first-page":"191","article-title":"The inherent compl. of dynamic data structures which accomodate range queries","author":"Fredman","year":"1980"},{"key":"10.1016\/0890-5401(89)90064-3_BIB14","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1145\/322276.322281","article-title":"A lower bound on the complexity of orthogonal range queries","volume":"28","author":"Fredman","year":"1981","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0890-5401(89)90064-3_BIB15","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0196-6774(81)90009-2","article-title":"The spanning bound as a measure of range query complexity","volume":"1","author":"Fredman","year":"1981","journal-title":"J. Algorithms"},{"key":"10.1016\/0890-5401(89)90064-3_BIB16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0210001","article-title":"Lower bounds on the complexity of some optimal data structures","volume":"10","author":"Fredman","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0890-5401(89)90064-3_BIB36","unstructured":"Fredman, M. L. (1985), private communidation, June."},{"key":"10.1016\/0890-5401(89)90064-3_BIB17","series-title":"1st ACM Com. Geom. Conference","first-page":"168","article-title":"Dynamization of geometric data structures","author":"Fries","year":"1985"},{"key":"10.1016\/0890-5401(89)90064-3_BIB18","series-title":"24th IEEE Symp. on FOCS","first-page":"282","article-title":"Tree structures for partial match retrieval","author":"Flajolet","year":"1983"},{"key":"10.1016\/0890-5401(89)90064-3_BIB19","series-title":"16th ACM STOC Symp.","first-page":"135","article-title":"Scaling and related techniques for geometry","author":"Gabow","year":"1984"},{"key":"10.1016\/0890-5401(89)90064-3_BIB20","series-title":"The 12th ICALP Symposium","first-page":"318","article-title":"The nearest neighbor problem on bounded domains","author":"Karlsson","year":"1985"},{"key":"10.1016\/0890-5401(89)90064-3_BIB21","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1137\/0215064","article-title":"Data structures for retrieval on square grids","volume":"15","author":"Katz","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0890-5401(89)90064-3_BIB22","doi-asserted-by":"crossref","first-page":"1072","DOI":"10.1109\/TC.1984.1676388","article-title":"Computational geometry a survey","volume":"33","author":"Lee","year":"1984","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/0890-5401(89)90064-3_BIB23","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF00263763","article-title":"Worst-case analysis of region and partial region searches in multi-dimensional binary search trees and balance quad trees","volume":"9","author":"Lee","year":"1977","journal-title":"Acta Inform."},{"key":"10.1016\/0890-5401(89)90064-3_BIB24","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1145\/320613.320618","article-title":"Quintary tree: A file structure for multidimensional database systems","volume":"5","author":"Lee","year":"1980","journal-title":"ACM Trans. Database Systems"},{"key":"10.1016\/0890-5401(89)90064-3_BIB25","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0020-0190(82)90119-3","article-title":"A data structure for dynamic range queries","volume":"15","author":"Lueker","year":"1982","journal-title":"Inform. Process Lett."},{"key":"10.1016\/0890-5401(89)90064-3_BIB26","first-page":"60","volume":"Vol. 3","author":"Mehlhorn","year":"1984"},{"key":"10.1016\/0890-5401(89)90064-3_BIB27","author":"Overmars","year":"1985"},{"key":"10.1016\/0890-5401(89)90064-3_BIB28","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF02241781","article-title":"Two general methods for dynamizing decomposable searching problems","volume":"26","author":"Overmars","year":"1981","journal-title":"Computing"},{"key":"10.1016\/0890-5401(89)90064-3_BIB29","author":"Preparata","year":"1985"},{"key":"10.1016\/0890-5401(89)90064-3_BIB30","series-title":"17th ACM STOC","first-page":"169","article-title":"Space time tradeoffs for orthogonal range queries","author":"Vaidya","year":"1985"},{"key":"10.1016\/0890-5401(89)90064-3_BIB31","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1137\/0211012","article-title":"Polygon retrieval","volume":"11","author":"Willard","year":"1982","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0890-5401(89)90064-3_BIB32","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1137\/0214019","article-title":"New data structure for orthogonal range queries","volume":"14","author":"Willard","year":"1985","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0890-5401(89)90064-3_BIB33_1","series-title":"2nd Symposium on Theoretical Aspects of Computer Science","first-page":"363","article-title":"Reduced memory space for multi-dimensional Serach trees","volume":"Vol. 182","author":"Willard","year":"1985"},{"key":"10.1016\/0890-5401(89)90064-3_BIB33_2","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1145\/31846.42228","volume":"34","author":"Willard","year":"1987","journal-title":"J. Assoc. Comp. Mach."},{"key":"10.1016\/0890-5401(89)90064-3_BIB34","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1145\/3828.3839","article-title":"Adding range restriction capability to dynamic data structures","volume":"32","author":"Willard","year":"1985","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0890-5401(89)90064-3_BIB35","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0214022","article-title":"On the complexity of maintaining partial sums","volume":"14","author":"Yao","year":"1985","journal-title":"SIAM J. Comput."}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0890540189900643?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0890540189900643?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,1]],"date-time":"2019-02-01T13:26:58Z","timestamp":1549027618000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0890540189900643"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,7]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1989,7]]}},"alternative-id":["0890540189900643"],"URL":"https:\/\/doi.org\/10.1016\/0890-5401(89)90064-3","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[1989,7]]}}}