{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:07:58Z","timestamp":1725664078183},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540582182"},{"type":"electronic","value":"9783540485773"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58218-5_2","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:36:40Z","timestamp":1330270600000},"page":"13-24","source":"Crossref","is-referenced-by-count":2,"title":["Selection in monotone matrices and computing k th nearest neighbors"],"prefix":"10.1007","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sandeep","family":"Sen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/BF01187037","volume":"9","author":"P. K. Agarwal","year":"1993","unstructured":"P.K. Agarwal, B. Aronov, M. Sharir and S. Suri, Selecting distances in the plane, Algorithmica 9 (1993), 495\u2013514.","journal-title":"Algorithmica"},{"key":"2_CR2","doi-asserted-by":"crossref","first-page":"794","DOI":"10.1137\/0222051","volume":"22","author":"P. K. Agarwal","year":"1993","unstructured":"P.K. Agarwal and J. Matou\u0161ek, Ray shooting and parametric search, SIAM J. Computing 22 (1993), 794\u2013806.","journal-title":"SIAM J. Computing"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"P.K. Agarwal and J. Matou\u0161ek, Range searching with semi-algebraic sets, Proc. 17th Symp. Mathematical Foundations of Computer Science, (Lecture Notes in Computer Science 629), Springer-Verlag 1992, pp. 1\u201313. (Also to appear in Discrete and Computational Geometry.)","DOI":"10.1007\/3-540-55808-X_1"},{"key":"2_CR4","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF01840359","volume":"2","author":"A. Aggarwal","year":"1987","unstructured":"A. Aggarwal, M. Klawe, S. Moran, P. Shor, and R. Wilber, Geometric applications of a matrix-searching algorithm, Algorithmica 2 (1987), 195\u2013208.","journal-title":"Algorithmica"},{"key":"2_CR5","unstructured":"A. Aggarwal and J. Park, Parallel searching in multidimensional monotone arrays, to appear in J. Algorithms."},{"key":"2_CR6","unstructured":"A. Aggarwal and J. Park, Sequential searching in multidimensional monotone arrays, to appear in J. Algorithms."},{"key":"2_CR7","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1287\/opre.41.3.549","volume":"41","author":"A. Aggarwal","year":"1993","unstructured":"A. Aggarwal and J. Park, Improved algorithm for economic lot size problems, Operations Research 41 (1993), 549\u2013571.","journal-title":"Operations Research"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, D. Kravets, J. Park, and S. Sen, Parallel searching in generalized Monge arrays with applications, Proc. 2nd ACM Symp. Parallel Algorithms and Architectures, 1990, pp. 259\u2013268.","DOI":"10.1145\/97444.97693"},{"key":"2_CR9","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0020-0190(90)90167-V","volume":"35","author":"A. Aggarwal","year":"1990","unstructured":"A. Aggarwal and S. Suri, Computing the longest diagonal of a simple polygon, Information Processing Letters 35 (1990), 13\u201318.","journal-title":"Information Processing Letters"},{"key":"2_CR10","unstructured":"N. Alon and Y. Azar, Comparison-sorting and selecting in totally monotone matrices, Proceedings 3rd Annual ACM-SIAM Symposium on Discrete Algorithms, 1992, pp. 403\u2013408."},{"key":"2_CR11","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01182772","volume":"11","author":"R. B. Yehuda","year":"1994","unstructured":"R. Bar Yehuda and S. Fogel, Variations on ray shooting, Algorithmica 11 (1994), 133\u2013145.","journal-title":"Algorithmica"},{"key":"2_CR12","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"M. Blum, R. Floyd, V. Pratt, R. Rivest, and R. Tarjan, Time bounds for selection, J. Computer and Systems Sciences 7 (1973), 448\u2013461.","journal-title":"J. Computer and Systems Sciences"},{"key":"2_CR13","unstructured":"P. Callahan and S. Kosaraju, Faster algorithms for some geometric graph problems in higher dimensions, Proceedings 4th Annual ACM-SIAM Symposium on Discrete Algorithms, 1993, pp. 291\u2013300."},{"key":"2_CR14","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. Preparata and C. Yap, New upper bounds for neighbor searching, Information and Control 68 (1986), 105\u2013124.","journal-title":"Information and Control"},{"key":"2_CR15","volume-title":"A Discipline of Programming","author":"E. Dijkstra","year":"1976","unstructured":"E. Dijkstra, A Discipline of Programming, Prentice-Hall, Englewood Cliff, NJ, 1976."},{"key":"2_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, Berlin, 1987."},{"key":"2_CR17","first-page":"463","volume":"2","author":"P. Erd\u0151s","year":"1935","unstructured":"P. Erd\u0151s and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463\u2013470.","journal-title":"Compositio Math."},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1137\/0213002","volume":"13","author":"G. Frederickson","year":"1984","unstructured":"G. Frederickson and D. Johnson, Generalized selection and ranking: sorted matrices, SIAM J. Computing 13 (1984), 14\u201330.","journal-title":"SIAM J. Computing"},{"key":"2_CR19","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1137\/0207013","volume":"7","author":"D. Johnson","year":"1978","unstructured":"D. Johnson and T. Mitzoguchi, Selecting the kth element in X+Y and X 1+X2+...+Xm, SIAM J. Computing 7 (1978), 147\u2013153.","journal-title":"SIAM J. Computing"},{"key":"2_CR20","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BF02090398","volume":"24","author":"D. Kravets","year":"1991","unstructured":"D. Kravets and J. Park, Selection and sorting in totally monotone arrays, Mathematical Systems Theory 24 (1991), 201\u2013220.","journal-title":"Mathematical Systems Theory"},{"key":"2_CR21","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1142\/S0218195993000087","volume":"3","author":"Y. Mansour","year":"1993","unstructured":"Y. Mansour, J. Park, B. Schieber and S. Sen, Improved selection in totally monotone arrays, International J. of Computational Geometry and Applications 3 (1993), 115\u2013132.","journal-title":"International J. of Computational Geometry and Applications"},{"key":"2_CR22","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0196-6774(92)90021-4","volume":"13","author":"J. Matou\u0161ek","year":"1992","unstructured":"J. Matou\u0161ek and E. Welzl, Good splitters for counting points in triangles, J. Algorithms 13 (1992), 307\u2013319.","journal-title":"J. Algorithms"},{"key":"2_CR23","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo, Applying parallel computation algorithms in the design of serial algorithms, J. ACM 30 (1983), 852\u2013865.","journal-title":"J. ACM"},{"key":"2_CR24","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"N. Sarnak, and R. E. Tarjan, Planar point location using persistent search trees, Comm. ACM 29 (1986), 609\u2013679.","journal-title":"Comm. ACM"},{"key":"2_CR25","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF02187718","volume":"4","author":"P. Vaidya","year":"1989","unstructured":"P. Vaidya, An O(n log n) algorithm for the all-nearest-neighbors problem, Discrete and Computational Geometry 4 (1989), 101\u2013115.","journal-title":"Discrete and Computational Geometry"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58218-5_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:18:46Z","timestamp":1605647926000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58218-5_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582182","9783540485773"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-58218-5_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}