{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:18:55Z","timestamp":1725664735151},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614227"},{"type":"electronic","value":"9783540685296"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_141","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:37:04Z","timestamp":1330292224000},"page":"309-320","source":"Crossref","is-referenced-by-count":2,"title":["Neighbours on a grid"],"prefix":"10.1007","author":[{"given":"Andrej","family":"Brodnik","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,7]]},"reference":[{"unstructured":"S. Albers and T. Hagerup. Improved parallel integer sorting without concurrent writting. In 3rd ACM-SIAM Symposium on Discrete Algorithms, pages 463\u2013172, Orlando, Florida, 1992.","key":"27_CR1"},{"doi-asserted-by":"crossref","unstructured":"A. Andersson, T. Hagerup, S. Nilsson, and R. Raman. Sorting in linear time? In 27th ACM Symposium on Theory of Computing, pages 427\u2013436, Las Vegas, Nevada, 1995.","key":"27_CR2","DOI":"10.1145\/225058.225173"},{"issue":"4","key":"27_CR3","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1145\/356789.356797","volume":"11","author":"J.L. Bentley","year":"1979","unstructured":"J.L. Bentley and J.H. Friedman. Data structures for range searching. ACM Computing Surveys, 11(4):397\u2013409, 1979.","journal-title":"ACM Computing Surveys"},{"key":"27_CR4","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF00263991","volume":"13","author":"J.L. Bentley","year":"1980","unstructured":"J.L. Bentley and H.A. Maurer. Efficient worst-case data structures for range searching. Acta Informatica, 13:155\u2013168, 1980.","journal-title":"Acta Informatica"},{"issue":"4","key":"27_CR5","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1145\/355921.355927","volume":"6","author":"J.L. Bentley","year":"1980","unstructured":"J.L. Bentley, B.W. Weide, and A.C. Yao. Optimal expected-time algorithms for closest-point problems. ACM Transactions on Mathematical Software, 6(4):563\u2013580, December 1980.","journal-title":"ACM Transactions on Mathematical Software"},{"unstructured":"A. Brodnik. Searching in Constant Time and Minimum Space (MINIM\/ARRES MAGNI MOMENTI SUNT). PhD thesis, University of Waterloo, Waterloo, Ontario, Canada, 1995. (Also published as technical report CS-95-41.).","key":"27_CR6"},{"issue":"8","key":"27_CR7","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1016\/0167-8655(93)90047-H","volume":"14","author":"C.-C. Chang","year":"1993","unstructured":"C.-C. Chang and T.-C. Wu. A bashing-oriented nearest neighbor searching scheme. Pattern Recognition Letters, 14(8):625\u2013630, August 1993.","journal-title":"Pattern Recognition Letters"},{"issue":"4","key":"27_CR8","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(83)90123-0","volume":"16","author":"B. Chazelle","year":"1983","unstructured":"B. Chazelle. An improved algorithm for the fixed-radius neighbor problem. Information Processing Letters, 16(4): 193\u2013198, May 13th 1983.","journal-title":"Information Processing Letters"},{"issue":"1\u20133","key":"27_CR9","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0019-9958(86)80030-4","volume":"68","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle, R. Cole, F.P. Preparata, and C. Yap. New upper bounds for neighbor searching. Information and Control, 68(1\u20133):105\u2013124, 1986.","journal-title":"Information and Control"},{"issue":"9","key":"27_CR10","doi-asserted-by":"crossref","first-page":"1412","DOI":"10.1109\/5.163409","volume":"80","author":"Y.-J. Chiang","year":"1992","unstructured":"Y.-J. Chiang and R. Tamassia. Dynamic algorithms in computational geometry. Proceedings of the IEEE, 80(9):1412\u20131434, September 1992.","journal-title":"Proceedings of the IEEE"},{"key":"27_CR11","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, Massachusetts, 1990."},{"issue":"1","key":"27_CR12","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1109\/TPAMI.1981.4767048","volume":"3","author":"C.R. Dyer","year":"1981","unstructured":"C.R. Dyer and A. Rosenfeld. Parallel image processing by memory-augmented cellular automata. IEEE Transactions on Pattern Analysis and Machine Intelligence, 3(1):29\u201341, January 1981.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"27_CR13","volume-title":"EATCS Monographs in Theoretical Computer Science","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner. Algorithms in Combinatorial Geometry. EATCS Monographs in Theoretical Computer Science. Springer-Verlag, Berlin, 1987."},{"key":"27_CR14","first-page":"1","volume-title":"Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity","author":"P. Emde Boas van","year":"1990","unstructured":"P. van Emde Boas. Machine models and simulations. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity, chapter 1, pages 1\u201366. Elsevier, Amsterdam, Holland, 1990."},{"issue":"1","key":"27_CR15","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10(1):99\u2013127, 1977.","journal-title":"Mathematical Systems Theory"},{"key":"27_CR16","first-page":"383","volume":"20","author":"A. Farag\u00f3","year":"1991","unstructured":"A. Farag\u00f3, T. Linder, and G. Lugosi. Nearest neighbor search and classification in O(1) time. Problems of Control and Information Theory, 20:383\u2013395, 1991.","journal-title":"Problems of Control and Information Theory"},{"key":"27_CR17","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M.L. Fredman","year":"1993","unstructured":"M.L. Fredman and D.E. Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences, 47:424\u2013436, 1993.","journal-title":"Journal of Computer and System Sciences"},{"unstructured":"R.G. Karlsson. Algorithms in a Restricted Universe. PhD thesis, University of Waterloo, Waterloo, Ontario, Canada, 1984. (Also published as technical report CS-84-50.).","key":"27_CR18"},{"doi-asserted-by":"crossref","unstructured":"R.G. Karlsson, J.I. Munro, and E.L. Robertson. The nearest neighbor problem on bounded domains. In W. Brauer, editor, Proceedings 12th International Colloquium on Automata, Languages and Programming, volume 194 of Lecture Notes in Computer Science, pages 318\u2013327. Springer-Verlag, 1985.","key":"27_CR19","DOI":"10.1007\/BFb0015757"},{"key":"27_CR20","volume-title":"The Art of Computer Programming: Sorting and Searching","author":"D.E. Knuth","year":"1973","unstructured":"D.E. Knuth. The Art of Computer Programming: Sorting and Searching, volume 3. Addison-Wesley, Reading, Massachusetts, 1973."},{"issue":"1","key":"27_CR21","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-storage applications. SIAM Journal on Computing, 9(1):200\u2013211, February 1980.","journal-title":"SIAM Journal on Computing"},{"key":"27_CR22","volume-title":"Data Structures and Algorithms: Multi-dimensional Searching and Computational Geometry","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Data Structures and Algorithms: Multi-dimensional Searching and Computational Geometry, volume 3. Springer-Verlag, Berlin, 1984."},{"issue":"2","key":"27_CR23","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1109\/TPAMI.1985.4767645","volume":"7","author":"R. Miller","year":"1985","unstructured":"R. Miller and Q.F. Stout. Geometric algorithms for digitized pictures on a mesh-connected computer. IEEE Transactions on Pattern Analysis and Machine Intelligence, 7(2):216\u2013228, March 1985.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"doi-asserted-by":"crossref","unstructured":"P.B. Miltersen. Lower bounds for union-split-find related problems on random access machines. In 26th ACM Symposium on Theory of Computing, pages 625\u2013634, Montr\u00e9al, Qu\u00e9bec, Canada, 1994.","key":"27_CR24","DOI":"10.1145\/195058.195415"},{"issue":"4","key":"27_CR25","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(86)90138-9","volume":"23","author":"O.J. Murphy","year":"1986","unstructured":"O.J. Murphy and S.M. Selkow. The efficiency of using k-d trees for finding nearest neighbors in discrete space. Information Processing Letters, 23(4):215\u2013218, November 8th 1986.","journal-title":"Information Processing Letters"},{"key":"27_CR26","volume-title":"Texts and Monographs in Computer Science","author":"F.P. Preparata","year":"1985","unstructured":"F.P. Preparata and M.I. Shamos. Computational Geometry. Texts and Monographs in Computer Science. Springer-Verlag, Berlin, 2nd edition, 1985.","edition":"2nd edition"},{"issue":"7","key":"27_CR27","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1016\/0167-8655(92)90064-7","volume":"13","author":"V. Ramasubramanian","year":"1992","unstructured":"V. Ramasubramanian and K.K. Paliwal. An efficient approximation-elimination algorithm for fast nearest-neighbour search based on a spherical distance coordinate formulation. Pattern Recognition Letters, 13(7):471\u2013480, July 1992.","journal-title":"Pattern Recognition Letters"},{"key":"27_CR28","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1007\/BF01759061","volume":"6","author":"R.F. Sproull","year":"1991","unstructured":"R.F. Sproull. Refinements to nearest-neighbor searching in k-dimensional trees. Algorithmica, 6:579\u2013589, 1991.","journal-title":"Algorithmica"},{"key":"27_CR29","first-page":"343","volume-title":"Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity","author":"F.F. Yao","year":"1990","unstructured":"F.F. Yao. Computational geometry. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity, chapter 7, pages 343\u2013389. Elsevier, Amsterdam, Holland, 1990."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61422-2_141.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:31:53Z","timestamp":1619573513000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_141","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}