{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:30:31Z","timestamp":1760441431071,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2017,10,31]],"date-time":"2017-10-31T00:00:00Z","timestamp":1509408000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2017,10,31]],"date-time":"2017-10-31T00:00:00Z","timestamp":1509408000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["612.001.118","024.002.003"],"award-info":[{"award-number":["612.001.118","024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["FT100100755","DP150101134"],"award-info":[{"award-number":["FT100100755","DP150101134"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00453-017-0384-3","type":"journal-article","created":{"date-parts":[[2017,10,31]],"date-time":"2017-10-31T15:06:37Z","timestamp":1509462397000},"page":"3253-3269","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Finding Pairwise Intersections Inside a Query Range"],"prefix":"10.1007","volume":"80","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":[[2017,10,31]]},"reference":[{"key":"384_CR1","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1016\/j.comgeo.2013.02.003","volume":"46","author":"M Abam","year":"2013","unstructured":"Abam, M., Carmi, P., Farshi, M., Smid, M.: On the power of semi-separated pair decomposition. Comput. Geom. 46, 631\u2013639 (2013)","journal-title":"Comput. Geom."},{"key":"384_CR2","doi-asserted-by":"crossref","unstructured":"Afshani, P., Arge, L., Larsen, K.D.: Orthogonal range reporting in three and higher dimensions. In: Proceedings of IEEE Symposium, pp. 149\u2013158 (2009)","DOI":"10.1109\/FOCS.2009.58"},{"key":"384_CR3","doi-asserted-by":"crossref","unstructured":"Afshani, P., Arge, L., Larsen, K.D.: Orthogonal range reporting: query lower bounds, optimal structures in 3-d, and higher-dimensional improvements. In: Proceedings of ACM Symposium on Computational Geometry, pp.\u00a0240\u2013246 (2010)","DOI":"10.1145\/1810959.1811001"},{"key":"384_CR4","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. Contemp. Math. 223, 1\u201356 (1999)","journal-title":"Contemp. Math."},{"issue":"2","key":"384_CR5","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."},{"issue":"3","key":"384_CR6","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(3), 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"key":"384_CR7","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":"384_CR8","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. Discrete Comput. Geom. 4, 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"key":"384_CR9","doi-asserted-by":"crossref","unstructured":"Davoodi, P., Smid, M., van Walderveen, F.: Two-dimensional range diameter queries. In: Proceedings of Latin American Symposium on Theoretical Informatics, pp. 219-230 (2012)","DOI":"10.1007\/978-3-642-29344-3_19"},{"issue":"1","key":"384_CR10","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s10852-010-9144-y","volume":"10","author":"AS Das","year":"2011","unstructured":"Das, A.S., Gupta, P., Srinathan, K.: Data structures for extension violations in a query range. J. Math. Model. Algorithms 10(1), 79\u2013107 (2011)","journal-title":"J. Math. Model. Algorithms"},{"key":"384_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M de Berg","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"384_CR12","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":"384_CR13","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. Vis. Graphics Image Proc. 28, 92\u2013108 (1984)","journal-title":"Comput. Vis. Graphics Image Proc."},{"key":"384_CR14","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":"384_CR15","unstructured":"Goodman, J.E., O\u2019Rourke, J.: Range searching. In: Handbook of Discrete and Computational Geometry, Chapter\u00a036, 2nd edn (2004)"},{"issue":"4","key":"384_CR16","first-page":"294","volume":"13","author":"P Gupta","year":"2006","unstructured":"Gupta, P.: Range-aggregate query problems involving geometric aggregation operations. Nord. J. Comput. 13(4), 294\u2013308 (2006)","journal-title":"Nord. J. Comput."},{"key":"384_CR17","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/j.comgeo.2009.08.001","volume":"47","author":"P Gupta","year":"2014","unstructured":"Gupta, P., Janardan, R., Kumar, Y., Smid, M.: Data structures for range-aggregate extent queries. Comput. Geom. Theory Appl. 47, 329\u2013347 (2014)","journal-title":"Comput. Geom. Theory Appl."},{"key":"384_CR18","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":"384_CR19","doi-asserted-by":"crossref","unstructured":"Rahul, S.: Improved bounds for orthogonal point enclosure query and point location in orthogonal subdivisions in $${\\mathbb{R}}^3$$. In: ACM-SIAM Symposium on Discrete Algorithms,\u00a0pp. 200\u2013211 (2015)","DOI":"10.1137\/1.9781611973730.15"},{"key":"384_CR20","unstructured":"Rahul, S.: Personal communication"},{"key":"384_CR21","doi-asserted-by":"crossref","unstructured":"Rahul, S., Das, A.S., Rajan, K.S., Srinatan, K.: Range-aggregate queries involving geometric aggregation operations. In: Workshop on Algorithms and Computation, vol. 1, pp. 122\u2013133 (2011)","DOI":"10.1007\/978-3-642-19094-0_14"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0384-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0384-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0384-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:30:57Z","timestamp":1589697057000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0384-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,31]]},"references-count":21,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["384"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0384-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,10,31]]},"assertion":[{"value":"27 May 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 October 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 October 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}