{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:56:30Z","timestamp":1767239790316,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030247652"},{"type":"electronic","value":"9783030247669"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-24766-9_20","type":"book-chapter","created":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T23:09:48Z","timestamp":1564528188000},"page":"269-282","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Range Closest-Pair Search in Higher Dimensions"],"prefix":"10.1007","author":[{"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[]},{"given":"Saladi","family":"Rahul","sequence":"additional","affiliation":[]},{"given":"Jie","family":"Xue","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"issue":"6","key":"20_CR1","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1016\/j.comgeo.2013.02.003","volume":"46","author":"MA Abam","year":"2013","unstructured":"Abam, M.A., Carmi, P., Farshi, M., Smid, M.: On the power of the semi-separated pair decomposition. Comput. Geom. 46(6), 631\u2013639 (2013)","journal-title":"Comput. Geom."},{"key":"20_CR2","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."},{"key":"20_CR3","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/j.jcss.2017.09.006","volume":"94","author":"PK Agarwal","year":"2018","unstructured":"Agarwal, P.K., Kumar, N., Sintos, S., Suri, S.: Range-max queries on uncertain data. J. Comput. Syst. Sci. 94, 118\u2013134 (2018)","journal-title":"J. Comput. Syst. Sci."},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"Won Bae, S., Smid, M.: Closest-pair queries in fat rectangles. CoRR arXiv:1809.10531 (2018)","DOI":"10.1016\/j.comgeo.2019.05.003"},{"key":"20_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03427-9","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. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-662-03427-9"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"Chan, T., Rahul, S., Xue, J.: Range closest-pair search higher dimensions. CoRR arXiv:1905.01029 (2019)","DOI":"10.1007\/978-3-030-24766-9_20"},{"issue":"4","key":"20_CR7","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1007\/s00224-013-9455-2","volume":"55","author":"TM Chan","year":"2014","unstructured":"Chan, T.M., Durocher, S., Larsen, K.G., Morrison, J., Wilkinson, B.T.: Linear-space data structures for range mode query in arrays. Theory Comput. Syst. 55(4), 719\u2013741 (2014)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"20_CR8","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B Chazelle","year":"1993","unstructured":"Chazelle, B.: Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom. 9(2), 145\u2013158 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"20_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-642-29344-3_19","volume-title":"LATIN 2012: Theoretical Informatics","author":"P Davoodi","year":"2012","unstructured":"Davoodi, P., Smid, M., van Walderveen, F.: Two-dimensional range diameter queries. In: Fern\u00e1ndez-Baca, D. (ed.) LATIN 2012. LNCS, vol. 7256, pp. 219\u2013230. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29344-3_19"},{"issue":"47","key":"20_CR10","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/j.comgeo.2009.08.001","volume":"2","author":"P Gupta","year":"2014","unstructured":"Gupta, P., Janardan, R., Kumar, Y., Smid, M.: Data structures for range-aggregate extent queries. Comput. Geom. 2(47), 329\u2013347 (2014)","journal-title":"Comput. Geom."},{"issue":"4","key":"20_CR11","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":"20_CR12","unstructured":"Kaplan, H., Rubin, N., Sharir, M., Verbin, E.: Counting colors in boxes. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 785\u2013794 (2007)"},{"issue":"3","key":"20_CR13","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF02293051","volume":"8","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Efficient partition trees. Discrete Comput. Geom. 8(3), 315\u2013334 (1992)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"20_CR14","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0925-7721(92)90006-E","volume":"2","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Reporting points in halfspaces. Comput. Geom. 2(3), 169\u2013186 (1992)","journal-title":"Comput. Geom."},{"issue":"1","key":"20_CR15","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/11084128X","volume":"43","author":"M P\u0103tra\u015fcu","year":"2014","unstructured":"P\u0103tra\u015fcu, M., Roditty, L.: Distance oracles beyond the Thorup-Zwick bound. SIAM J. Comput. 43(1), 300\u2013311 (2014)","journal-title":"SIAM J. Comput."},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Rahul, S., Janardan, R.: Algorithms for range-skyline queries. In: Proceedings of ACM Symposium on Advances in Geographic Information Systems (GIS), pp. 526\u2013529 (2012)","DOI":"10.1145\/2424321.2424406"},{"key":"20_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/978-3-540-45072-6_15","volume-title":"Advances in Spatial and Temporal Databases","author":"J Shan","year":"2003","unstructured":"Shan, J., Zhang, D., Salzberg, B.: On spatial-range closest-pair query. In: Hadzilacos, T., Manolopoulos, Y., Roddick, J., Theodoridis, Y. (eds.) SSTD 2003. LNCS, vol. 2750, pp. 252\u2013269. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45072-6_15"},{"key":"20_CR18","unstructured":"Sharathkumar, R., Gupta, P.: Range-aggregate proximity queries. Technical report TR\/2007\/80, IIIT Hyderabad, Telangana (2007)"},{"key":"20_CR19","first-page":"877","volume-title":"Handbook of Computational Geometry","author":"M Smid","year":"1999","unstructured":"Smid, M.: Closest point problems in computational geometry. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 877\u2013935. Elsevier Science, Amsterdam (1999)"},{"key":"20_CR20","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/1.9781611975482.24","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Jie Xue","year":"2019","unstructured":"Xue, J.: Colored range closest-pair problem under general distance functions. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 373\u2013390 (2019)"},{"key":"20_CR21","unstructured":"Xue, J., Li, Y., Janardan, R.: Approximate range closest-pair search. In: Proceedings of the Canadian Conference on Computational Geometry (CCCG), pp. 282\u2013287 (2018)"},{"key":"20_CR22","unstructured":"Xue, J., Li, Y., Rahul, S., Janardan, R.: New bounds for range closest-pair problems. In: Proceedings of Symposium on Computational Geometry (SoCG), pp. 73:1\u201373:14. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing (2018)"},{"key":"20_CR23","unstructured":"Xue, J., Li, Y., Rahul, S., Janardan, R.: Searching for the closest-pair in a query translate. CoRR arXiv:1807.09498 (2018)"}],"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-030-24766-9_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T17:54:19Z","timestamp":1710266059000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-24766-9_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030247652","9783030247669"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-24766-9_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Edmonton, AB","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}