{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T19:34:33Z","timestamp":1771961673057,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540602200","type":"print"},{"value":"9783540447474","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60220-8_48","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:53:05Z","timestamp":1330278785000},"page":"26-37","source":"Crossref","is-referenced-by-count":8,"title":["On some geometric selection and optimization problems via sorted matrices"],"prefix":"10.1007","author":[{"given":"Alex","family":"Glozman","sequence":"first","affiliation":[]},{"given":"Klara","family":"Kedem","sequence":"additional","affiliation":[]},{"given":"Gregory","family":"Shpitalnik","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/BF01182774","volume":"11","author":"P. Agarwal","year":"1994","unstructured":"P. Agarwal and M. Sharir. \u201cPlanar geometric location problems\u201d, Algorithmica, 11(1994), pp 185\u2013195.","journal-title":"Algorithmica"},{"key":"3_CR2","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1972","unstructured":"M. Blum, R.W. Floyd, V.R. Pratt, R.L. Rivest and Tarjan, R.E. \u201cTime bounds for selection\u201d, J. Comput. Syst. Sci., 7(1972), pp. 448\u2013461.","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"R. Cole","year":"1981","unstructured":"R. Cole. \u201cSearching and storing similar lists\u201d, J. Comput. Syst. Sci., 23(1981), pp. 166\u2013204.","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"B. Chazelle. \u201cNew techniques for computing order statistics in Euclidean space\u201d, Proc. 1st ACM Symp. on Computational Geometry, 1985, pp. 125\u2013134.","DOI":"10.1145\/323233.323251"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"L. P. Chew and K. Kedem. \u201cImprovements on Geometric Pattern Matching Problems\u201d, SWAT, LNCS 621, Springer-Verlag, 1992, pp. 318\u2013325.","DOI":"10.1007\/3-540-55706-7_28"},{"key":"3_CR6","unstructured":"G.N. Frederickson. \u201cOptimal algorithms for tree partitioning\u201d, Proc. 2nd ACM-SIAM. Symp. on Discrete Algorithms, 1991, pp. 168\u2013177."},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0022-0000(82)90048-4","volume":"24","author":"G. N. Frederickson","year":"1982","unstructured":"G. N. Frederickson and D. B. Johnson. \u201cThe complexity of selection and ranking in X+Y and matrices with sorted columns\u201d, J. Comput. Syst. Sci., 24(1982), pp. 197\u2013208.","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0196-6774(83)90035-4","volume":"4","author":"G. N. Frederickson","year":"1983","unstructured":"G. N. Frederickson and D. B. Johnson. \u201cFinding k th paths and p-center by generating and searching good data structures\u201d, J. Algorithms, 4(1983), pp. 61\u201380.","journal-title":"J. Algorithms"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1137\/0213002","volume":"13","author":"G. N. Frederickson","year":"1984","unstructured":"G. N. Frederickson and D. B. Johnson. \u201cGeneralized selection and ranking: sorted matrices.\u201d, SIAM J. Computing, 13(1984), pp. 14\u201330.","journal-title":"SIAM J. Computing"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"M. Houle and G. Toussaint, \u201cComputing the width of a set\u201d, Proc. 1st ACM Symp. on Computational Geometry, 1985, pp. 1\u20137.","DOI":"10.1145\/323233.323234"},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/0196-6774(91)90013-O","volume":"12","author":"J. Hershberger","year":"1991","unstructured":"J. Hershberger and S. Suri. \u201cFinding Tailored Partitions\u201d, J. Algorithms, 12(1991), pp. 431\u2013463.","journal-title":"J. Algorithms"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"M.J. Katz, \u201cImproved algorithms in geometric optimization via expanders\u201d, Proc. 3rd Israel Symposium on Theory of Computing and Systems, 1995, to appear.","DOI":"10.1109\/ISTCS.1995.377043"},{"key":"3_CR13","unstructured":"D. Kravets and J. Park. \u201cSelection and Sorting in Totally Monotone Arrays\u201d, Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, 1990, pp. 494\u2013502."},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"M.J. Katz and M. Sharir, \u201cAn expander-based approach to geometric optimization\u201d, Proc. 9th ACM Symp. on Computational Geometry, 1993, pp. 198\u2013207.","DOI":"10.1145\/160985.161137"},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo. \u201cApplying parallel computation algorithms in the design of serial algorithms.\u201d, J. ACM, 30(1983), pp. 852\u2013865.","journal-title":"J. ACM"},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0020-0190(89)90166-X","volume":"30","author":"J. S. Salowe","year":"1989","unstructured":"J. S. Salowe. \u201cL-infinity interdistance selection by parametric search\u201d, Inf. Proc. Lett., 30(1989), pp. 9\u201314.","journal-title":"Inf. Proc. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60220-8_48.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:56:06Z","timestamp":1605646566000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60220-8_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602200","9783540447474"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-60220-8_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}