{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T13:18:25Z","timestamp":1776086305442,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1987,9,1]],"date-time":"1987-09-01T00:00:00Z","timestamp":557452800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[1987,9]]},"DOI":"10.1007\/bf00263295","type":"journal-article","created":{"date-parts":[[2004,9,27]],"date-time":"2004-09-27T12:15:17Z","timestamp":1096287317000},"page":"565-582","source":"Crossref","is-referenced-by-count":6,"title":["Some techniques for geometric searching with implicit set representations"],"prefix":"10.1007","volume":"24","author":[{"given":"Bernard","family":"Chazelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1987,9,1]]},"reference":[{"key":"BF00263295_CR1","volume-title":"The design and analysis of computer algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer algorithms. Reading, MA, Addison-Wesley 1974"},{"key":"BF00263295_CR2","unstructured":"Bentley, J.L., Shamos, M.I.: Divide-and-conquer in multidimensional space. Proc. 8th Ann. ACM Symp. Theory Comput. (1976), pp. 220\u2013230"},{"key":"BF00263295_CR3","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1972","unstructured":"Blum, M., Floyd, R.W., Pratt, V.R., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci. 7, 448\u2013161 (1972)","journal-title":"J. Comput. Syst. Sci."},{"key":"BF00263295_CR4","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B.: Filtering search: A new approach to query-answering. SIAM J. Comput. 15, 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"key":"BF00263295_CR5","first-page":"145","volume-title":"Proc. CAAP'85, Berlin, LNCS","author":"B. Chazelle","year":"1985","unstructured":"Chazelle, B.: Fast searching in a real algebraic manifold with applications to geometric complexity. Proc. CAAP'85, Berlin, LNCS, pp 145\u2013156. Berlin, Heidelberg, New York: Springer Verlag 1985"},{"key":"BF00263295_CR6","doi-asserted-by":"crossref","unstructured":"Chazelle, B.: New techniques for computing order statistics in Euclidean space. Proc. ACM Symp. Comput. Geometry, pp. 125\u2013134, 1985","DOI":"10.1145\/323233.323251"},{"key":"BF00263295_CR7","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BF01840441","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B., Guibas, L.J.: Fractional cascading: II. Applications. Algorithmica 1, 163\u2013191 (1986)","journal-title":"Algorithmica"},{"key":"BF00263295_CR8","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/BF01934990","volume":"25","author":"B. Chazelle","year":"1985","unstructured":"Chazelle, B., Guibas, L.J., Lee, D.T.: The power of geometric duality. BIT 25, 76\u201390 (1985)","journal-title":"BIT"},{"key":"BF00263295_CR9","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0020-0190(84)90073-5","volume":"18","author":"F. Chin","year":"1984","unstructured":"Chin, F., Wang, C.A.: Minimum vertex distance between separable convex polygons. Inf. Proc. Lett. 18, 41\u201345 (1984)","journal-title":"Inf. Proc. Lett."},{"key":"BF00263295_CR10","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1016\/0196-6774(86)90004-0","volume":"7","author":"R. Cole","year":"1986","unstructured":"Cole, R.: Searching and storing similar lists. J. Algorithms 7, 202\u2013220 (1986)","journal-title":"J. Algorithms"},{"key":"BF00263295_CR11","doi-asserted-by":"crossref","unstructured":"Cole, R.: Slowing down sorting networks to obtain faster sorting algorithms. Proc. of 25th Ann. IEEE Symp. Found. Comput. Sci., pp. 255\u2013259. Singer Island 1984","DOI":"10.1109\/SFCS.1984.715923"},{"key":"BF00263295_CR12","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0019-9958(84)80040-6","volume":"63","author":"R. Cole","year":"1984","unstructured":"Cole, R., Yap, C.K.: Geometric retrieval problems. Inf. Control 63, 39\u201357 (1984)","journal-title":"Inf. Control"},{"key":"BF00263295_CR13","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0205015","volume":"5","author":"D.P. Dobkin","year":"1976","unstructured":"Dobkin, D.P., Lipton, R.J.: Multidimensional searching problems. SIAM J. Comput. 5, 181\u2013186 (1976)","journal-title":"SIAM J. Comput."},{"key":"BF00263295_CR14","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., O'Rourke, J., Seidel, R.: Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput. 15, 341\u2013363 (1986)","journal-title":"SIAM J. Comput."},{"key":"BF00263295_CR15","series-title":"Rep. F111, Inst. Inform. Proc.","volume-title":"0.695Halfplanar range search in linear space and O(n) query time","author":"H. Edelsbrunner","year":"1983","unstructured":"Edelsbrunner, H., Welzl, E.: Halfplanar range search in linear space and O(n 0.695) query time. Rep. F111, Inst. Inform. Proc., Techn. Univ. Graz, Austria 1983"},{"key":"BF00263295_CR16","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0022-0000(82)90048-4","volume":"24","author":"G.N. Frederickson","year":"1982","unstructured":"Frederickson, G.N., Johnson, D.B.: The complexity of selection and ranking in X+Y and matrices with sorted columns. J. Comput. Syst. Sci. 24, 197\u2013208 (1982)","journal-title":"J. Comput. Syst. Sci."},{"key":"BF00263295_CR17","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0196-6774(83)90035-4","volume":"4","author":"G.N. Frederickson","year":"1983","unstructured":"Frederickson, G.N., Johnson, D.B.: Finding k th paths and p-centers by generating and searching good data structures. J. Algorithms. 4, 61\u201380 (1983)","journal-title":"J. Algorithms."},{"key":"BF00263295_CR18","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1137\/0213002","volume":"13","author":"G.N. Frederickson","year":"1984","unstructured":"Frederickson, G.N., Johnson, D.B.: Generalized selection and ranking: sorted matrices. SIAM J. Comput 13, 14\u201330 (1984)","journal-title":"SIAM J. Comput"},{"key":"BF00263295_CR19","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1145\/322108.322114","volume":"26","author":"Z. Galil","year":"1979","unstructured":"Galil, Z., Megiddo, N.: A fast selection algorithm and the problem of optimum distribution of effort. J. ACM 26, 58\u201364 (1979)","journal-title":"J. ACM"},{"key":"BF00263295_CR20","doi-asserted-by":"crossref","unstructured":"Haussler, D., Welzl, E.: Epsilon-nets and simplex range queries. Proc. 2nd Annu. ACM Symp. Comput. Geometry, pp. 61\u201371 (1986)","DOI":"10.1145\/10515.10522"},{"key":"BF00263295_CR21","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1137\/0207013","volume":"7","author":"D.B. Johnson","year":"1978","unstructured":"Johnson, D.B., Mizoguchi, T.: Selecting the k-th element in X + Y and X1+X2+...+Xm. SIAM J. Comput. 7, 147\u2013153 (1978)","journal-title":"SIAM J. Comput."},{"key":"BF00263295_CR22","unstructured":"McKenna, M., Toussaint, G.T.: Finding the minimum vertex distance between two disjoint convex polygons in linear time. Tech. Rep. SOCS-83-6, McGill University, 1983"},{"key":"BF00263295_CR23","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1145\/2157.322410","volume":"vol. 30","author":"N. Meggido","year":"1983","unstructured":"Meggido, N.: Applying parallel computation algorithms in the design of serial algorithms. J. ACM, 852\u2013865 (1983), vol. 30","journal-title":"J. ACM"},{"key":"BF00263295_CR24","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1137\/0210023","volume":"10","author":"N. Meggido","year":"1981","unstructured":"Meggido, N., Tamir, A., Zemel, E., Chandrasekaran, R.: An O(n log2 n) algorithm for the k th longest path in a tree with applications to location problems. SIAM J. Comput. 10, 328\u2013337 (1981)","journal-title":"SIAM J. Comput."},{"key":"BF00263295_CR25","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/0020-0190(85)90123-1","volume":"20","author":"A. Mirzaian","year":"1985","unstructured":"Mirzaian, A., Arjomandi, E.: Selection in X+Y and matrices with sorted rows and columns. Inf. Proc. Lett. 20, 13\u201317 (1985)","journal-title":"Inf. Proc. Lett."},{"key":"BF00263295_CR26","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1145\/359423.359430","volume":"20","author":"F.P. Preparata","year":"1977","unstructured":"Preparata, F.P., Hong, S.J.: Convex hulls of finite sets of points in two and three dimensions. Commun. ACM 20, 87\u201393 (1977)","journal-title":"Commun. ACM"},{"key":"BF00263295_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational geometry","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational geometry. Berlin, Heidelberg, New York: Springer 1985"},{"key":"BF00263295_CR28","unstructured":"Salowe, J.S.: Efficient geometric selection in the plane. M. Sc. Thesis, Rutgers University, 1985"},{"key":"BF00263295_CR29","first-page":"251","volume-title":"Algorithms and complexity: new directions and recent results","author":"M.I. Shamos","year":"1976","unstructured":"Shamos, M.I.: Geometry and statistics: problems at the interface, in: Algorithms and complexity: new directions and recent results, J.F. Traub (ed.), pp. 251\u2013280. New York: Academic Press 1976"},{"key":"BF00263295_CR30","doi-asserted-by":"crossref","unstructured":"Tarski, A.: A decision method for elementary algebra and geometry. Univ. of Calif. Press, 1948, 2nd Ed., 1951","DOI":"10.1525\/9780520348097"},{"key":"BF00263295_CR31","unstructured":"Toussaint, G.T.: An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons. Proc. 21st Allerton Conf. Comm. Control Comput., pp 457\u2013458 (1983)"},{"key":"BF00263295_CR32","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1137\/0211012","volume":"11","author":"D.E. Willard","year":"1982","unstructured":"Willard, D.E.: Polygon retrieval. SIAM J. Comput 11, 149\u2013165 (1982)","journal-title":"SIAM J. Comput"},{"key":"BF00263295_CR33","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/0211059","volume":"11","author":"A.C. Yao","year":"1982","unstructured":"Yao, A.C.: On constructing minimum spanning tree in k-dimensional space and related problems. SIAM J. Comput. 11, 721\u2013736 (1982)","journal-title":"SIAM J. Comput."},{"key":"BF00263295_CR34","doi-asserted-by":"crossref","unstructured":"Yao, A.C., Yao, F.F.: A general approach to d-dimensional geometric queries, 17th Ann. ACM Symp. Theory Comput., pp. 163\u2013168. Providence, RI, 1985","DOI":"10.1145\/22145.22163"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00263295.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00263295\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00263295","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00263295.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T19:08:24Z","timestamp":1734548904000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00263295"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,9]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1987,9]]}},"alternative-id":["BF00263295"],"URL":"https:\/\/doi.org\/10.1007\/bf00263295","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,9]]}}}