{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:49:12Z","timestamp":1742914152286,"version":"3.40.3"},"publisher-location":"Cham","reference-count":14,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319218397"},{"type":"electronic","value":"9783319218403"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21840-3_20","type":"book-chapter","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T09:57:38Z","timestamp":1437991058000},"page":"236-248","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Finding Pairwise Intersections Inside a Query Range"],"prefix":"10.1007","author":[{"given":"Mark","family":"de Berg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Gudmundsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ali D.","family":"Mehrabi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,28]]},"reference":[{"key":"20_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/conm\/223\/03131","volume":"223","author":"PK Agarwal","year":"1999","unstructured":"Agarwal, P.K., Erickson, J.: Geometric range searching and its relatives. Contemporary Mathematics 223, 1\u201356 (1999)","journal-title":"Contemporary Mathematics"},{"issue":"2","key":"20_CR2","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1137\/120891241","volume":"43","author":"B Aronov","year":"2014","unstructured":"Aronov, B., de Berg, M., Ezra, E., Sharir, M.: Improved bounds for the union of locally fat objects in the plane. SIAM J. Comput. 43(2), 543\u2013572 (2014)","journal-title":"SIAM J. Comput."},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer (2008)","DOI":"10.1007\/978-3-540-77974-2"},{"key":"20_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":"20_CR5","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B Chazelle","year":"1988","unstructured":"Chazelle, B.: A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput. 17, 427\u2013462 (1988)","journal-title":"SIAM J. Comput."},{"key":"20_CR6","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/BF01182771","volume":"11","author":"B Chazelle","year":"1994","unstructured":"Chazelle, B., Edelsbrunner, H., Guibas, L.J., Sharir, M.: Algorithms for bichromatic line-segment problems and polyhedral terrains. Algorithmica 11, 116\u2013132 (1994)","journal-title":"Algorithmica"},{"key":"20_CR7","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"KL Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry. II. Discr. Comput. Geom. I 4, 387\u2013421 (1989)","journal-title":"II. Discr. Comput. Geom. I"},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H Edelsbrunner","year":"1986","unstructured":"Edelsbrunner, H., Guibas, L.J., Stolfi, J.: Optimal point location in a monotone subdivision. SIAM J. Comput. 15, 317\u2013340 (1986)","journal-title":"SIAM J. Comput."},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0734-189X(84)90142-7","volume":"28","author":"H Edelsbrunner","year":"1984","unstructured":"Edelsbrunner, H., Overmars, M.H., Seidel, R.: Some methods of computational geometry applied to computer graphics. Comput. Vision, Graphics and Image Proc. 28, 92\u2013108 (1984)","journal-title":"Comput. Vision, Graphics and Image Proc."},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of $$O(n^2)$$ problems in computational geometry. Comput. Geom. Theory Appl. 5, 165\u2013185 (1995)","journal-title":"Comput. Geom. Theory Appl."},{"key":"20_CR11","unstructured":"Goodman, J.E., O\u2019Rourke, J.: Range Searching. Handbook of Discrete and Computational Geometry, 2nd edn., Chapter 36 (2004)"},{"key":"20_CR12","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF02187683","volume":"1","author":"K Keden","year":"1986","unstructured":"Keden, K., Livne, R., Pach, J., Sharir, M.: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discr. Comput. Geom. 1, 59\u201371 (1986)","journal-title":"Discr. Comput. Geom."},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"Rahul, S., Das, A.S., Rajan, K.S., Srinatan, K.: Range-aggregate queries involving geometric aggregation operations. In: Proc. Workshop on Alg. Comp. vol. 1, pp. 122\u2013133 (2011)","DOI":"10.1007\/978-3-642-19094-0_14"},{"key":"20_CR14","unstructured":"Subramanian, S., Ramaswamy, S.: The P-range tree: A new data structure for range searching in secondary memory. In: Proc. 6th ACM-SIAM Symp. Discr. Alg., pp. 378\u2013387 (1995)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21840-3_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T05:46:50Z","timestamp":1676958410000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21840-3_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319218397","9783319218403"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21840-3_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}