{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T17:25:31Z","timestamp":1743009931021,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540139126"},{"type":"electronic","value":"9783540391364"}],"license":[{"start":{"date-parts":[[1984,1,1]],"date-time":"1984-01-01T00:00:00Z","timestamp":441763200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1984]]},"DOI":"10.1007\/bfb0024008","type":"book-chapter","created":{"date-parts":[[2005,11,19]],"date-time":"2005-11-19T00:44:22Z","timestamp":1132361062000},"page":"187-196","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Proximity on a grid"],"prefix":"10.1007","author":[{"given":"Rolf G.","family":"Karlsson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. Ian","family":"Munro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,18]]},"reference":[{"issue":"4","key":"20_CR1","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"J.L. Bentley","year":"1980","unstructured":"J.L. Bentley and J.B. Saxe, Decomposable Searching Problems I. Static-to-Dynamic Transformations, J. Algorithms 1, 4 (Dec. 1980), 301\u2013358.","journal-title":"J. Algorithms"},{"issue":"2","key":"20_CR2","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1137\/0205015","volume":"5","author":"D.P. Dobkin","year":"1976","unstructured":"D.P. Dobkin and R.J. Lipton, Multidimensional Searching Problems, SIAM J. Comput. 5, 2 (June 1976), 181\u2013186.","journal-title":"SIAM J. Comput."},{"key":"20_CR3","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0020-0190(83)90045-5","volume":"17","author":"L.J. Guibas","year":"1983","unstructured":"L.J. Guibas and J. Stolfi, On Computing All North-East Nearest Neighbors in the L\n1 Metric, Information Processing Lett. 17 (Nov. 1983), 219\u2013223.","journal-title":"Information Processing Lett."},{"key":"20_CR4","unstructured":"R.G. Karlsson, Algorithms on Bounded Domains, Ph.D. dissertation in preparation (1984)."},{"key":"20_CR5","unstructured":"J.M. Keil and D.G. Kirkpatrick, Computational Geometry on Integer Grids, Allerton Conference 1981, 41\u201350."},{"key":"20_CR6","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D.G. Kirkpatrick","year":"1983","unstructured":"D.G. Kirkpatrick, Optimal Search in Planar Subdivisions, SIAM J.Comput. 12 (Feb. 1983), 28\u201335.","journal-title":"SIAM J.Comput."},{"key":"20_CR7","volume-title":"The Art of Computer Programming, Vol. 3, Sorting and Searching","author":"D.E. Knuth","year":"1973","unstructured":"D.E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching, Addison-Wesley, Reading, Mass., 1973."},{"key":"20_CR8","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1137\/0209017","volume":"9","author":"D.T. Lee","year":"1980","unstructured":"D.T. Lee and C.K. Wong, Voronoi Diagrams in L\n1 (L\n\u221e) metrics with 2-dimensional storage applications, SIAM J.Comput. 9 (Feb. 1980), 200\u2013211.","journal-title":"SIAM J.Comput."},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"R.J. Lipton and R.E. Tarjan, Applications of a Planar Separator Theorem, Proc. 18th Annual IEEE Symposium on Foundations of Computer Science (1978), 28\u201334.","DOI":"10.1109\/SFCS.1977.6"},{"issue":"4","key":"20_CR10","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/0020-0190(81)90093-4","volume":"12","author":"M.H. Overmars","year":"1981","unstructured":"M.H. Overmars and J. van Leeuwen, Worst-case Optimal Insertion and Deletion Methods for Decomposable Searching Problems, Information Processing Lett. 12, 4 (Aug. 1981), 168\u2013173.","journal-title":"Information Processing Lett."},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"M.I. Shamos, Geometric Complexity, Proc. 7th Annual ACM Symposium on Theory of Computing (1975), 224\u2013233.","DOI":"10.1145\/800116.803772"},{"key":"20_CR12","unstructured":"D.E. Willard, Two Very Fast Trie Data Structures, Allerton Conference 1981, 355\u2013363."},{"key":"20_CR13","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D.E. Willard","year":"1983","unstructured":"D.E. Willard, Log-logarithmic Worst-case Range Queries Are Possible in Space \u0398(n), Information Processing Lett. 17 (Aug. 1983), 81\u201384.","journal-title":"Information Processing Lett."}],"container-title":["Lecture Notes in Computer Science","STACS 85"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0024008","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T23:31:00Z","timestamp":1578526260000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0024008"}},"subtitle":["Preliminary version"],"short-title":[],"issued":{"date-parts":[[1984]]},"ISBN":["9783540139126","9783540391364"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/bfb0024008","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1984]]},"assertion":[{"value":"18 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}