{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T22:36:17Z","timestamp":1790807777450,"version":"4.1.0"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1986,3,1]],"date-time":"1986-03-01T00:00:00Z","timestamp":510019200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1986,3]]},"DOI":"10.1007\/bf02187685","type":"journal-article","created":{"date-parts":[[2005,9,20]],"date-time":"2005-09-20T14:09:34Z","timestamp":1127225374000},"page":"83-93","source":"Crossref","is-referenced-by-count":32,"title":["Halfspace range search: An algorithmic application ofk-sets"],"prefix":"10.1007","volume":"1","author":[{"given":"B.","family":"Chazelle","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"F. P.","family":"Preparata","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[1986,3,1]]},"reference":[{"key":"BF02187685_CR1","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(79)90117-0","volume":"8","author":"J. L. Bentley","year":"1979","unstructured":"J. L. Bentley and H. A. Maurer, A note on Euclidean near neighbor searching in the plane, Inform. Process. Lett. 8 (1979), 133\u2013136.","journal-title":"Inform. Process. Lett."},{"key":"BF02187685_CR2","doi-asserted-by":"crossref","unstructured":"B. Chazelle, Filtering search: A new approach to query-answering, Proc. 24th IEEE Annu. Symp. Found. Comput. Sci., (1983), 122\u2013132 (also to appear in J. SIAM on Comput.)","DOI":"10.1109\/SFCS.1983.17"},{"key":"BF02187685_CR3","unstructured":"B. Chazelle, Criticality considerations in the design of geometric algorithms, Proc. 22nd Annu. Allerton Conf. on Comm., Contr., and Comput. (1984)."},{"key":"BF02187685_CR4","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 Univ."},{"key":"BF02187685_CR5","doi-asserted-by":"crossref","unstructured":"B. Chazelle, L. J. Guibas, and D. T. Lee, The power of geometric duality, Proc. 24th IEEE Annu. Symp. Found. Comput. Sci., (1983), 217\u2013225.","DOI":"10.1109\/SFCS.1983.75"},{"key":"BF02187685_CR6","doi-asserted-by":"crossref","unstructured":"R. Cole, M. Sharir, and C. K. Yap, Onk-hulls and related problems, Proc. 16th Annu. ACM Symp. on Theory of Computing, (1984), 154\u2013166. To appear in SIAM J. on Comput.","DOI":"10.1145\/800057.808677"},{"key":"BF02187685_CR7","doi-asserted-by":"crossref","unstructured":"R. Cole and C. K. Yap, Geometric retrieval problems, Proc. 24th IEEE Annu. Symp. Found. Comput. Sci., (1983), 112\u2013121.","DOI":"10.1109\/SFCS.1983.22"},{"key":"BF02187685_CR8","unstructured":"H. Edelsbrunner, Arrangements and geometric computations, to appear."},{"key":"BF02187685_CR9","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner, J. O'Rourke, and R. Seidel, Constructing arrangements of lines and hyperplanes with applications, Proc. 24th IEEE Annu. Symp. Found. Comput. Sci., (1983), 83\u201391.","DOI":"10.1109\/SFCS.1983.11"},{"key":"BF02187685_CR10","doi-asserted-by":"crossref","unstructured":"P. Erd\u0151s, L. Lov\u00e1sz, A. Simmons, and E. G. Straus, Dissection graphs of planar point sets, in A Survey of Combinatorial Theory, J. N. Srivastava et al., eds., North-Holland (1973), 139\u2013149.","DOI":"10.1016\/B978-0-7204-2262-7.50018-1"},{"issue":"6","key":"BF02187685_CR11","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1109\/TC.1982.1676031","volume":"C-31","author":"D. T. Lee","year":"1982","unstructured":"D. T. Lee, Onk-nearest neighbor Voronoi diagrams in the plane, IEEE Trans. Comp., Vol C-31, No. 6, June 1982, pp. 478\u2013487.","journal-title":"IEEE Trans. Comp."},{"key":"BF02187685_CR12","unstructured":"F. P. Preparata and M. I. Shamos, Introduction to Computational Geometry, Springer-Verlag, to appear."},{"key":"BF02187685_CR13","unstructured":"F. F. Yao, D. P. Dobkin, and H. Edelsbrunner, A partition of 3-space with applications, forthcoming report."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187685.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02187685\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187685","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T13:54:16Z","timestamp":1586440456000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02187685"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,3]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1986,3]]}},"alternative-id":["BF02187685"],"URL":"https:\/\/doi.org\/10.1007\/bf02187685","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,3]]}}}