{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:46:27Z","timestamp":1740109587334,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","license":[{"start":{"date-parts":[[2022,9,6]],"date-time":"2022-09-06T00:00:00Z","timestamp":1662422400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,9,6]],"date-time":"2022-09-06T00:00:00Z","timestamp":1662422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-11-17336","CCF-12-18791"],"award-info":[{"award-number":["CCF-11-17336","CCF-12-18791"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-15-40656"],"award-info":[{"award-number":["CCF-15-40656"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2014\/170"],"award-info":[{"award-number":["2014\/170"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100016382","name":"Schmidt Family Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100016382","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009328","name":"Planning and Budgeting Committee of the Council for Higher Education of Israel","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100009328","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005005","name":"Ben-Gurion University of the Negev","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005005","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1884\/16"],"award-info":[{"award-number":["1884\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2014\/170"],"award-info":[{"award-number":["2014\/170"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-12-18791"],"award-info":[{"award-number":["CCF-12-18791"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"DOI":"10.1007\/s00454-022-00433-5","type":"journal-article","created":{"date-parts":[[2022,9,6]],"date-time":"2022-09-06T14:03:41Z","timestamp":1662473021000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Bipartite Diameter and Other Measures Under Translation"],"prefix":"10.1007","author":[{"given":"Boris","family":"Aronov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3978-1428","authenticated-orcid":false,"given":"Omrit","family":"Filtser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew J.","family":"Katz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Khadijeh","family":"Sheikhan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,9,6]]},"reference":[{"issue":"5","key":"433_CR1","doi-asserted-by":"publisher","first-page":"1867","DOI":"10.1137\/120900708","volume":"42","author":"PK Agarwal","year":"2013","unstructured":"Agarwal, P.K., Aronov, B., van Kreveld, M., L\u00f6ffler, M., Silveira, R.I.: Computing correlation between piecewise-linear functions. SIAM J. Comput. 42(5), 1867\u20131887 (2013)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"433_CR2","doi-asserted-by":"publisher","first-page":"#\u00a071","DOI":"10.1145\/1824777.1824791","volume":"6","author":"PK Agarwal","year":"2010","unstructured":"Agarwal, P.K., Har-Peled, S., Sharir, M., Wang, Y.: Hausdorff distance under translation for points and balls. ACM Trans. Algorithms 6(4), #\u00a071 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"433_CR3","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/BF02712871","volume":"16","author":"PK Agarwal","year":"1996","unstructured":"Agarwal, P.K., Sharir, M.: Efficient randomized algorithms for some geometric optimization problems. Discrete Comput. Geom. 16(4), 317\u2013337 (1996)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"433_CR4","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1006\/jagm.1994.1038","volume":"17","author":"PK Agarwal","year":"1994","unstructured":"Agarwal, P.K., Sharir, M., Toledo, S.: Applications of parametric searching in geometric optimization. J. Algorithms 17(3), 292\u2013318 (1994)","journal-title":"J. Algorithms"},{"issue":"2","key":"433_CR5","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.comgeo.2007.08.001","volume":"40","author":"H-K Ahn","year":"2008","unstructured":"Ahn, H.-K., Brass, P., Shin, C.-S.: Maximum overlap and minimum convex hull of two convex polyhedra under translations. Comput. Geom. 40(2), 171\u2013177 (2008)","journal-title":"Comput. Geom."},{"issue":"3","key":"433_CR6","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/BF02187910","volume":"3","author":"H Alt","year":"1988","unstructured":"Alt, H., Mehlhorn, K., Wagener, H., Welzl, E.: Congruence, similarity, and symmetries of geometric objects. Discrete Comput. Geom. 3(3), 237\u2013256 (1988)","journal-title":"Discrete Comput. Geom."},{"key":"433_CR7","unstructured":"Aronov, B., Filtser, O., Katz, M.J., Sheikhan, K.: Bipartite diameter and other measures under translation. In: 36th International Symposium on Theoretical Aspects of Computer Science (Berlin 2019). Leibniz International Proceedings in Informatics, vol. 126, #8. Leibniz-Zentrum f\u00fcr Informatik, Wadern (2019)"},{"key":"433_CR8","doi-asserted-by":"crossref","unstructured":"Ben-Avraham, R., Henze, M., Jaume, R., Keszegh, B., Raz, O.E., Sharir,\u00a0M., Tubis,\u00a0I.: Minimum partial-matching and Hausdorff RMS-distance under translation: combinatorics and algorithms. In: 22nd European Symposium on Algorithms (Wroc\u0142aw 2014). Lecture Notes in Computer Science, vol. 8737, pp. 100\u2013111. Springer, Heidelberg (2014)","DOI":"10.1007\/978-3-662-44777-2_9"},{"key":"433_CR9","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. Springer, Berlin (2008)"},{"issue":"9","key":"433_CR10","doi-asserted-by":"publisher","first-page":"1662","DOI":"10.1016\/j.patcog.2006.01.003","volume":"39","author":"A Bishnu","year":"2006","unstructured":"Bishnu, A., Das, S., Nandy, S.C., Bhattacharya, B.B.: Simple algorithms for partial point set pattern matching under rigid motion. Pattern Recogn. 39(9), 1662\u20131671 (2006)","journal-title":"Pattern Recogn."},{"key":"433_CR11","unstructured":"Brown, K.Q.: Geometric Transforms for Fast Geometric Algorithms. PhD thesis, Carnegie-Mellon University (1980)"},{"key":"433_CR12","unstructured":"Chan, T.M.: An optimal randomized algorithm for maximum Tukey depth. In: 15th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2004), pp. 430\u2013436. ACM, New York (2004)"},{"issue":"2","key":"433_CR13","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(2), 116\u2013132 (1994)","journal-title":"Algorithmica"},{"issue":"2","key":"433_CR14","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1145\/201019.201036","volume":"42","author":"KL Clarkson","year":"1995","unstructured":"Clarkson, K.L.: Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM 42(2), 488\u2013499 (1995)","journal-title":"J. ACM"},{"issue":"5","key":"433_CR15","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(5), 387\u2013421 (1989)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"433_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-001-0016-8","volume":"31","author":"A Efrat","year":"2001","unstructured":"Efrat, A., Itai, A., Katz, M.J.: Geometry helps in bottleneck matching and related problems. Algorithmica 31(1), 1\u201328 (2001)","journal-title":"Algorithmica"},{"key":"433_CR17","doi-asserted-by":"crossref","unstructured":"Erickson, J.: New lower bounds for halfspace emptiness. In: 37th Annual Symposium on Foundations of Computer Science (Burlington 1996), pp. 472\u2013481. IEEE Computer Society Press, Los Alamitos (1996)","DOI":"10.1109\/SFCS.1996.548506"},{"issue":"2","key":"433_CR18","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/BF02187878","volume":"2","author":"LJ Guibas","year":"1987","unstructured":"Guibas, L.J., Seidel, R.: Computing convolutions by reciprocal search. Discrete Comput. Geom. 2(2), 175\u2013193 (1987)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"433_CR19","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0925-7721(94)90004-3","volume":"4","author":"PJ Heffernan","year":"1994","unstructured":"Heffernan, P.J., Schirra, S.: Approximate decision algorithms for point set congruence. Comput. Geom. 4(3), 137\u2013156 (1994)","journal-title":"Comput. Geom."},{"issue":"5","key":"433_CR20","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1109\/34.6790","volume":"10","author":"ME Houle","year":"1988","unstructured":"Houle, M.E., Toussaint, G.T.: Computing the width of a set. IEEE Trans. Pattern Anal. Mach. Intell. 10(5), 761\u2013765 (1988)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"3","key":"433_CR21","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/BF02189323","volume":"9","author":"DP Huttenlocher","year":"1993","unstructured":"Huttenlocher, D.P., Kedem, K., Sharir, M.: The upper envelope of Vorono\u012d surfaces and its applications. Discrete Comput. Geom. 9(3), 267\u2013291 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"433_CR22","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0925-7721(02)00095-0","volume":"24","author":"P Indyk","year":"2003","unstructured":"Indyk, P., Venkatasubramanian, S.: Approximate congruence in nearly linear time. Comput. Geom. 24(2), 115\u2013128 (2003)","journal-title":"Comput. Geom."},{"issue":"4","key":"433_CR23","doi-asserted-by":"publisher","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N Megiddo","year":"1983","unstructured":"Megiddo, N.: Linear-time algorithms for linear programming in $\\mathbf{R}^3$ and related problems. SIAM J. Comput. 12(4), 759\u2013776 (1983)","journal-title":"SIAM J. Comput."},{"key":"433_CR24","doi-asserted-by":"crossref","unstructured":"Ramos, E.A.: Deterministic algorithms for 3-D diameter and some 2-D lower envelopes. In: 16th Annual Symposium on Computational Geometry (Hong Kong 2000), pp. 290\u2013299. ACM, New York (2000)","DOI":"10.1145\/336154.336215"},{"key":"433_CR25","unstructured":"Shamos, M.I.: Computational Geometry. PhD thesis, Yale University (1978)"},{"key":"433_CR26","doi-asserted-by":"crossref","unstructured":"Sharir, M., Welzl, E.: A combinatorial bound for linear programming and related problems. In: 9th Annual Symposium on Theoretical Aspects of Computer Science (Cachan 1992). Lecture Notes in Computer Science, vol. 577, pp. 569\u2013579. Springer, Berlin (1992)","DOI":"10.1007\/3-540-55210-3_213"},{"key":"433_CR27","doi-asserted-by":"crossref","unstructured":"Welzl, E.: Smallest enclosing disks (balls and ellipsoids). In: New Results and New Trends in Computer Science (Graz 1991). Lecture Notes in Computer Science, vol. 555, pp. 359\u2013370. Springer, Berlin (1991)","DOI":"10.1007\/BFb0038202"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00433-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00433-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00433-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,3]],"date-time":"2024-10-03T09:14:04Z","timestamp":1727946844000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00433-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,6]]},"references-count":27,"alternative-id":["433"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00433-5","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2022,9,6]]},"assertion":[{"value":"13 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 June 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 June 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 September 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}