{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T13:18:24Z","timestamp":1776086304621,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1993,5,1]],"date-time":"1993-05-01T00:00:00Z","timestamp":736214400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1993,5]]},"DOI":"10.1007\/bf01187037","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T17:11:10Z","timestamp":1108746670000},"page":"495-514","source":"Crossref","is-referenced-by-count":40,"title":["Selecting distances in the plane"],"prefix":"10.1007","volume":"9","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boris","family":"Aronov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Subhash","family":"Suri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"Technical Report 90-58","author":"P. K. Agarwal","year":"1990","unstructured":"P. K. Agarwal and M. Sharir, Planar geometric location problems, Technical Report 90-58, DIMACS, Rutgers University, New Brunswick, NJ, August 1990. (Also to appear inAlgorithmica)."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"28","author":"J. L. Bentley","year":"1979","unstructured":"J. L. Bentley and T. Ottmann, Algorithms for reporting and counting geometric intersections,IEEE Trans. Comput. 28 (1979), 643?647.","journal-title":"IEEE Trans. Comput."},{"key":"CR3","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. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan, Time bounds for selection,J. Comput. System Sci. 7 (1973), 448?461.","journal-title":"J. Comput. System Sci."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/BF00263295","volume":"24","author":"B. Chazelle","year":"1987","unstructured":"B. Chazelle, Some techniques for geometric searching with implicit set representations,Acta Inform.24 (1987), 565?682.","journal-title":"Acta Inform"},{"key":"CR5","first-page":"1","volume":"1","author":"B. Chazelle","year":"1968","unstructured":"B. Chazelle and D. T. Lee, On a circle placement problem,Computing 1 (1968), 1?16.","journal-title":"Computing"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"K. Clarkson","year":"1989","unstructured":"K. Clarkson and P. Shor, Applications of random sampling in computational geometry, II,Discrete Comput. Geom. 4 (1989), 387?421.","journal-title":"Discrete Comput. Geom."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1145\/7531.7537","volume":"34","author":"R. Cole","year":"1987","unstructured":"R. Cole. Slowing down sorting networks to obtain faster sorting algorithms,J. Assoc. Comput. Mach. 34 (1987), 200?208.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R. Cole","year":"1986","unstructured":"R. Cole and U. Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking,Inform. and Control 70 (1986), 32?53.","journal-title":"Inform. and Control"},{"key":"CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"A lgorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner,A lgorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0304-3975(92)90319-B","volume":"92","author":"H. Edelsbrunner","year":"1992","unstructured":"H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir, Arrangements of curves in the plane: Combinatorics, topology and algorithms,Theoret. Comput. Sci. 92 (1992), 319?336.","journal-title":"Theoret. Comput. Sci."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, L. J. Guibas, and J. Stolfi, Optimal point location in a monotone subdivision,SIAM J. Comput. 15 (1986), 317?340.","journal-title":"SIAM J. Comput."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1145\/322217.322232","volume":"27","author":"M. Fischer","year":"1980","unstructured":"M. Fischer and L. Ladner, Parallel prefix computation,J. Assoc. Comput. Mach. 27 (1980), 831?838.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579170","volume":"6","author":"S. Hart","year":"1986","unstructured":"S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path-compression schemes,Combinatorica 6 (1986), 151?177.","journal-title":"Combinatorica"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"J. Matou?ek, Approximations and optimal geometric divide-and-conquer,Proc. 23rd Annual ACM Symposium on Theory of Computing, 1991, pp. 506?511.","DOI":"10.1145\/103418.103470"},{"key":"CR15","doi-asserted-by":"crossref","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. Assoc. Comput. Mach. 30 (1983), 852?865.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1016\/0196-6774(85)90011-2","volume":"6","author":"N. Megiddo","year":"1985","unstructured":"N. Megiddo, Partition with two lines in the plane,J. Algorithms 6 (1985), 430?433.","journal-title":"J. Algorithms"},{"key":"CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F. Preparata","year":"1985","unstructured":"F. Preparata and M. Shamos,Computational Geometry: An Introduction, Springer-Verlag, Heidelberg, 1985."},{"key":"CR18","volume-title":"Ph.D. Thesis","author":"J. Salowe","year":"1987","unstructured":"J. Salowe, Selection problems in computational geometry, Ph.D. Thesis, Department of Computer Science, Rutgers University, New Brunswick, NJ, 1987."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/S0022-0000(76)80029-3","volume":"13","author":"A. Sch\u00f6nhage","year":"1976","unstructured":"A. Sch\u00f6nhage, M. Paterson, and N. Pippenger, Finding the median,J. Comput. Systems Sci. 13(1976), 184?199.","journal-title":"J. Comput. Systems Sci."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","volume":"2","author":"Y. Shiloach","year":"1981","unstructured":"Y. Shiloach and U. Vishkin, Finding the maximum, merging and sorting in a parallel computation model,J. Algorithms 2 (1981), 88?102.","journal-title":"J. Algorithms"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1137\/0220045","volume":"20","author":"R. Tamassia","year":"1991","unstructured":"R. Tamassia and J. S. Vitter, Parallel transitive closure and point location in planar structures,SIAM J. Comput. 20 (1991), 708?725.","journal-title":"SIAM J. Comput."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R. Tarjan","year":"1985","unstructured":"R. Tarjan and U. Vishkin, An efficient parallel biconnectivity algorithm,SIAM J. Comput. 14 (1985), 862?874.","journal-title":"SIAM J. Comput."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1137\/0204030","volume":"4","author":"L. Valiant","year":"1975","unstructured":"L. Valiant, Parallelism in comparison problems,SIAM J. Comput. 4 (1975), 348?355.","journal-title":"SIAM J. Comput."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"A. Yao","year":"1982","unstructured":"A. Yao, On constructing minimum spanning tree ink-dimensional space and related problems,SIAM J. Comput. 11 (1982), 721?736.","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01187037.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01187037\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01187037","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T21:17:51Z","timestamp":1586121471000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01187037"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,5]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1993,5]]}},"alternative-id":["BF01187037"],"URL":"https:\/\/doi.org\/10.1007\/bf01187037","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,5]]}}}