{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T01:14:48Z","timestamp":1772846088008,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1986,11,1]],"date-time":"1986-11-01T00:00:00Z","timestamp":531187200000},"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":[[1986,11]]},"DOI":"10.1007\/bf01840441","type":"journal-article","created":{"date-parts":[[2005,7,13]],"date-time":"2005-07-13T21:29:13Z","timestamp":1121290153000},"page":"163-191","source":"Crossref","is-referenced-by-count":94,"title":["Fractional cascading: II. Applications"],"prefix":"10.1007","volume":"1","author":[{"given":"Bernard","family":"Chazelle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonidas J.","family":"Guibas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"BF01840441_CR1","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/358841.358850","volume":"23","author":"J. L. Bentley","year":"1880","unstructured":"J. L. Bentley.Multidimensional divide and conquer. Commun. ACM,23, 4 (1880), 214\u2013229.","journal-title":"Commun. ACM"},{"key":"BF01840441_CR2","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"J. L. Bentley","year":"1980","unstructured":"J. L. Bentley and J. B. Saxe.Decomposable searching problems I: static to dynamic transformations. J. Algorithms,1 (1980), 301\u2013358.","journal-title":"J. Algorithms"},{"key":"BF01840441_CR3","unstructured":"J. L. Bentley and M. I. Shamos.A problem in multivariate statistics: Algorithms, datastructures and applications. Proc. 15th Allerton Conf. Comm., Contr., and Comput. (1977), 193\u2013201."},{"key":"BF01840441_CR4","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1109\/TC.1980.1675628","volume":"C-29","author":"J. L. Bentley","year":"1980","unstructured":"J. L. Bentley and D. Wood.An Optimal worst-case algorithm for reporting intersections of rectangles. IEEE Trans. Comput.,C-29 (1980), 571\u2013577.","journal-title":"IEEE Trans. Comput."},{"key":"BF01840441_CR5","doi-asserted-by":"crossref","unstructured":"B. Chazelle.Filtering search: A new approach to query-answering. Proc. 24th Ann. Symp. Found. Comput. Sci. (1983), 122\u2013132. To appear in SIAM J. Comput. (1986).","DOI":"10.1137\/0215051"},{"key":"BF01840441_CR6","doi-asserted-by":"crossref","unstructured":"B. Chazelle.How to search in history. Inform, and Control (1985).","DOI":"10.1016\/S0019-9958(85)80045-0"},{"key":"BF01840441_CR7","unstructured":"B. Chazelle.A functional approach to data structures and its use in multidimensional searching. Brown Univ. Tech. Rept, CS-85-16, Sept. 1985 (preliminary version in 26th FOCS, 1985)."},{"key":"BF01840441_CR8","series-title":"Tech. Rept. CS-84-11","volume-title":"New upper bounds for neighbor searching","author":"B. Chazelle","year":"1984","unstructured":"B. Chazelle, R. Cole, F. P. Preparata, and C. K. Yap.New upper bounds for neighbor searching. Tech. Rept. CS-84-11 (1984), Brown University, Providence, RI."},{"key":"BF01840441_CR9","doi-asserted-by":"crossref","unstructured":"B. Chazelle and H. Edelsbrunner.Linear space data structures for a class of range search. To appear in Proc. 2nd ACM Symposium on Computational Geometry, 1986.","DOI":"10.1145\/10515.10547"},{"key":"BF01840441_CR10","doi-asserted-by":"crossref","unstructured":"B. Chazelle and L. J. Guibas.Visibility and intersection problems in plane geometry. Proc. 1st ACM Symposium on Computational Geometry, Baltimore, MD, June 1985, pp. 135\u2013146.","DOI":"10.1145\/323233.323252"},{"key":"BF01840441_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01934990","volume":"25","author":"B. Chazelle","year":"1985","unstructured":"B. Chazelle, L. J. Guibas, and D. T. Lee.The power of geometric duality. BIT,25, 1, (1985). Also, in Proc. 24th Ann. Symp. Found. Comp. Sci. (1983), 217\u2013225.","journal-title":"BIT"},{"key":"BF01840441_CR12","series-title":"Tech. Report No.","volume-title":"Searching and storing similar lists","author":"R. Cole","year":"1983","unstructured":"R. Cole.Searching and storing similar lists. Tech. Report No. 88, Courant Inst., New York University, New York, Oct. 1983. To appear in J. Algorithms."},{"key":"BF01840441_CR13","doi-asserted-by":"crossref","unstructured":"R. Cole and C. K. Yap.Geometric retrieval problems, Proc. 24th Ann. Symp. Found. Comput. Sci. (1983), 112\u2013121.","DOI":"10.1109\/SFCS.1983.22"},{"key":"BF01840441_CR14","unstructured":"D. P. Dobkin and H. Edelsbrunner.Space searching for intersection objects. Proc. 25th Ann. Symp. Found. Comput. Sci. (1984)."},{"key":"BF01840441_CR15","doi-asserted-by":"crossref","unstructured":"D. P. Dobkin and J. I. Munro.Efficient uses of the past. Proc. 21st Ann. Symp. Found. Comput. Sci. (1980), 200\u2013206.","DOI":"10.1109\/SFCS.1980.18"},{"key":"BF01840441_CR16","series-title":"Tech. Report, Rep.","volume-title":"Ph.D. Thesis","author":"H. Edelsbrunner","year":"1982","unstructured":"H. Edelsbrunner.Intersection problems in computational geometry. Ph.D. Thesis, Tech. Report, Rep. 93, IIG, Univ. Graz, Austria, 1982."},{"key":"BF01840441_CR17","unstructured":"H. Edelsbrunner, L. J. Guibas, and J. Stolfi.Optimal point location in a monotone subdivision. To appear."},{"key":"BF01840441_CR18","volume-title":"Forthcoming technical report","author":"H. Edelsbrunner","year":"1984","unstructured":"H. Edelsbrunner and F. Huber.Dissecting sets of points in two and three dimensions. Forthcoming technical report, IIG, University of Graz, Austria, 1984."},{"key":"BF01840441_CR19","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1016\/0020-0190(82)90090-4","volume":"14","author":"H. Edelsbrunner","year":"1982","unstructured":"H. Edelsbrunner, D. G. Kirkpatrick, and H. A. Maurer.Polygonal intersection search. In-form. Process. Lett.14 (1982), 74\u201379.","journal-title":"In-form. Process. Lett"},{"key":"BF01840441_CR20","series-title":"Tech. Report, F-111, IIG","volume-title":"Halfplanar range search in linear space and O(n0.695)query time","author":"H. Edelsbrunner","year":"1983","unstructured":"H. Edelsbrunner and E. Welzl.Halfplanar range search in linear space and O(n0.695)query time. Tech. Report, F-111, IIG, University of Graz, Austria 1983."},{"key":"BF01840441_CR21","doi-asserted-by":"crossref","unstructured":"H. N. Gabow, J. L. Bentley, and R. E. Tarjan.Scaling and related techniques for geometry problems. Proc. 16th Ann. SIGACT Symp. (1984), 135\u2013143.","DOI":"10.1145\/800057.808675"},{"key":"BF01840441_CR22","volume-title":"The art of computer programming, sorting and searching, Vol. 3","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth.The art of computer programming, sorting and searching, Vol. 3. Addison-Wesley, Reading, MA, 1973."},{"issue":"3","key":"BF01840441_CR23","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1137\/0206043","volume":"6","author":"D. T. Lee","year":"1977","unstructured":"D. T. Lee and F. P. Preparata.Location of a point in a planar subdivision and its applications. SIAM J. Comput,6, 3 (1977), 594\u2013606.","journal-title":"SIAM J. Comput"},{"key":"BF01840441_CR24","unstructured":"E. M. McCreight.Efficient algorithms for enumerating intersecting intervals and rectangles. Tech. Rep., Xerox PARC, CSL-80-9 (June 1980)."},{"key":"BF01840441_CR25","unstructured":"E. M. McCreight.Priority search trees. Tech. Rep., Xerox PARC, CSL-81-5 (1981)."},{"key":"BF01840441_CR26","volume-title":"PhD Thesis","author":"M. H. Overmars","year":"1983","unstructured":"M. H. Overmars.The design of dynamic data structures. PhD Thesis, University of Utrecht, The Netherlands, 1983."},{"key":"BF01840441_CR27","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/0022-0000(79)90042-4","volume":"18","author":"R. E. Tarjan","year":"1979","unstructured":"R. E. Tarjan.A class of algorithms which require nonlinear time to maintain disjoint sets. J. Comput. System Sci.,18 (1979), 110\u2013127.","journal-title":"J. Comput. System Sci."},{"key":"BF01840441_CR28","unstructured":"D. E. Willard.New data structures for orthogonal queries. To appear in SIAM J. Comput."},{"key":"BF01840441_CR29","doi-asserted-by":"crossref","unstructured":"F. F. Yao.A 3-space partition and its applications. Proc. 15th Annual SIGACT Symp. (1983), 258\u2013263.","DOI":"10.1145\/800061.808755"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840441.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01840441\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840441","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T06:58:58Z","timestamp":1586329138000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01840441"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,11]]},"references-count":29,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1986,11]]}},"alternative-id":["BF01840441"],"URL":"https:\/\/doi.org\/10.1007\/bf01840441","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,11]]}}}