{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T04:17:25Z","timestamp":1749010645876,"version":"3.41.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T00:00:00Z","timestamp":1465516800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T00:00:00Z","timestamp":1465516800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["CCF-1422324","IIS-1422591"],"award-info":[{"award-number":["CCF-1422324","IIS-1422591"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["CNS-1547167"],"award-info":[{"award-number":["CNS-1547167"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,7]]},"DOI":"10.1007\/s00453-016-0173-4","type":"journal-article","created":{"date-parts":[[2016,6,10]],"date-time":"2016-06-10T15:32:10Z","timestamp":1465572730000},"page":"741-770","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["FPTAS for Minimizing the Earth Mover\u2019s Distance Under Rigid Transformations and Related Problems"],"prefix":"10.1007","volume":"78","author":[{"given":"Hu","family":"Ding","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinhui","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,6,10]]},"reference":[{"key":"173_CR1","doi-asserted-by":"crossref","unstructured":"Alt, H., Behrends, B., Blomer, J.: Approximate matching of polygonal shapes (Extended Abstract). In: Proceedings of the 7th ACM Symposium on Computational Geometry (SoCG\u201991), pp.\u00a0186\u2013193 (1991)","DOI":"10.1145\/109648.109669"},{"key":"173_CR2","first-page":"121","volume-title":"Handbook of Computational Geometry","author":"H Alt","year":"1999","unstructured":"Alt, H., Guibas, L.: Discrete geometric shapes: matching, interpolation, and approximation. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 121\u2013153. Elsevier, Amsterdam (1999)"},{"key":"173_CR3","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, 237\u2013256 (1988)","journal-title":"Discrete Comput. Geom."},{"key":"173_CR4","unstructured":"Andoni, A., Indyk, P., Krauthgamer, R.: Earth mover\u2019s distance over high-dimensional spaces. In: Proccedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908), pp.\u00a0343\u2013352 (2008)"},{"key":"173_CR5","doi-asserted-by":"crossref","unstructured":"Andoni, A., Do Ba, K., Indyk, P., Woodruff, D.P.: Efficient sketches for earth mover\u2019s distance, with applications. In: Proccedings 50th IEEE Symposium on Foundations of Computer Science (FOCS\u201909), pp.\u00a0324\u2013330 (2009)","DOI":"10.1109\/FOCS.2009.25"},{"key":"173_CR6","doi-asserted-by":"crossref","unstructured":"Andoni, A., Onak, K., Nikolov, A., Yaroslavtsev, G.: Parallel Algorithms for Geometric Graph Problems. In: Proccedings of the 46th Symposium on Theory of Computing Conference (STOC\u201914), pp. 574\u2013583 (2014)","DOI":"10.1145\/2591796.2591805"},{"issue":"5","key":"173_CR7","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1109\/TPAMI.1987.4767965","volume":"9","author":"KS Arun","year":"1987","unstructured":"Arun, K.S., Huang, T.S., Blostein, S.D.: Least-squares fitting of two 3-D point sets. IEEE Trans. Pattern Anal. Mach. Intell 9(5), 698\u2013700 (1987)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell"},{"issue":"4","key":"173_CR8","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1287\/ijoc.4.4.375","volume":"4","author":"EM Arkin","year":"1992","unstructured":"Arkin, E.M., Kedem, K., Mitchell, J.S.B., Sprinzak, J., Werman, M.: Matching points into pairwise-disjoint noise regions: combinatorial bounds and algorithms. INFORMS J. Comput. 4(4), 375\u2013386 (1992)","journal-title":"INFORMS J. Comput."},{"key":"173_CR9","unstructured":"Agarwal, P.K., Phillips, J.M.: On bipartite matching under the RMS distance. In: Proccedings of the 18th Canadian Conference on Computational Geometry (CCCG\u201906) (2006)"},{"issue":"2","key":"173_CR10","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1109\/34.121791","volume":"14","author":"PJ Besl","year":"1992","unstructured":"Besl, P.J., McKay, N.D.: A method for registration of 3-D shapes. IEEE Trans. Pattern Anal. Mach. Intell. 14(2), 239\u2013256 (1992)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"173_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jda.2012.03.002","volume":"15","author":"M Benkert","year":"2012","unstructured":"Benkert, M., Gudmundsson, J., Merrick, D., Wolle, T.: Approximate one-to-one point pattern matching. J. Discrete Algorithms 15, 1\u201315 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"173_CR12","unstructured":"Cohen, S.: Finding color and shape patterns in images. PhD thesis, Stanford University, Department of Compute Science (1999)"},{"key":"173_CR13","doi-asserted-by":"crossref","unstructured":"Chew, L.P., Dor, D., Efrat, A., Kedem, K.: Geometric pattern matching in d-dimensional space. In: Proccedings of the 3rd European Symposium on Algorithms (ESA\u201995), pp.\u00a0 264\u2013279 (1995)","DOI":"10.1007\/3-540-60313-1_149"},{"key":"173_CR14","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0925-7721(95)00047-X","volume":"7","author":"LP Chew","year":"1997","unstructured":"Chew, L.P., Goodrich, M.T., Huttenlocher, D.P., Kedem, K., Kleinberg, J.M., Kravets, D.: Geometric pattern matching under euclidean motion. Comput. Geom. 7, 113\u2013124 (1997)","journal-title":"Comput. Geom."},{"issue":"2","key":"173_CR15","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.ipl.2007.08.003","volume":"105","author":"S Cabello","year":"2008","unstructured":"Cabello, S., Giannopoulos, P., Knauer, C.: On the parameterized complexity of d-dimensional point set pattern matching. Inf. Process. Lett. 105(2), 73\u201377 (2008)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"173_CR16","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/j.comgeo.2006.10.001","volume":"39","author":"S Cabello","year":"2008","unstructured":"Cabello, S., Giannopoulos, P., Knauer, C., Rote, G.: Matching point sets with respect to the earth mover\u2019s distance. Comput. Geom.: Theory Appl. 39(2), 118\u2013133 (2008)","journal-title":"Comput. Geom.: Theory Appl."},{"key":"173_CR17","doi-asserted-by":"crossref","unstructured":"Cardoze, D.E., Schulman, L.J.: Pattern matching for spatial point sets. In: Proccedings of the 39th IEEE Symposium on Foundations of Computer Science (FOCS\u201998), pp.\u00a0156\u2013165 (1998)","DOI":"10.1109\/SFCS.1998.743439"},{"issue":"16","key":"173_CR18","doi-asserted-by":"publisher","first-page":"2351","DOI":"10.1093\/bioinformatics\/btu307","volume":"30","author":"C Clark","year":"2014","unstructured":"Clark, C., Kalita, J.: A comparison of algorithms for the pairwise alignment of biological networks. Bioinformatics 30(16), 2351\u20132359 (2014)","journal-title":"Bioinformatics"},{"key":"173_CR19","doi-asserted-by":"crossref","unstructured":"Efrat, A., Itai, A.: Improvements on bottleneck matching and related problems using geometry. In: Proccedings of the 12th ACM Symposium on Computational Geometry (SoCG\u201996), pp.\u00a0301\u2013310 (1996)","DOI":"10.1145\/237218.237399"},{"issue":"1\u20132","key":"173_CR20","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.comgeo.2007.10.007","volume":"41","author":"E Ezra","year":"2008","unstructured":"Ezra, E., Sharir, M., Efrat, A.: On the performance of the ICP algorithm. Comput. Geom. 41(1\u20132), 77\u201393 (2008)","journal-title":"Comput. Geom."},{"key":"173_CR21","doi-asserted-by":"crossref","unstructured":"Graumann, K., Darell, T.: Fast contour matching using approximate earth mover\u2019s distance. IEEE Conference on Computer Vision and Pattern Recognition (CVPR\u201904), pp.\u00a0 220\u2013227 (2004)","DOI":"10.1109\/CVPR.2004.1315035"},{"issue":"1","key":"173_CR22","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00453-003-1043-4","volume":"38","author":"M Gavrilov","year":"2004","unstructured":"Gavrilov, M., Indyk, P., Motwani, R., Venkatasubramanian, S.: Combinatorial and experimental methods for approximate point pattern matching. Algorithmica 38(1), 59\u201390 (2004)","journal-title":"Algorithmica"},{"issue":"4","key":"173_CR23","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1109\/34.761267","volume":"21","author":"MT Goodrich","year":"1999","unstructured":"Goodrich, M.T., Mitchell, J.S.B., Orletsky, M.W.: Approximate geometric pattern matching under rigid motions. IEEE Trans. Pattern Anal. Mach. Intell. 21(4), 371\u2013379 (1999)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"173_CR24","doi-asserted-by":"crossref","unstructured":"Giannopoulos, P., Veltkamp, R.: A pseudo-metric for weighted point sets. In: Proccedings of 7th European Conference Computer Vision (ECCV\u201902), pp.\u00a0715\u2013731 (2002)","DOI":"10.1007\/3-540-47977-5_47"},{"key":"173_CR25","doi-asserted-by":"crossref","unstructured":"Huttenlocher, D.P., Kedem, K., Kleinberg, J.M.: On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane. In: Proccedings of the 8th ACM Symposium on Computational Geometry (SoCG\u201992), pp.\u00a0110\u2013119 (1992)","DOI":"10.1145\/142675.142700"},{"key":"173_CR26","unstructured":"Indyk, P.: A near linear time constant factor approximation for Euclidean bichromatic matching (cost). In: Proccedings of the 8th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907), pp.\u00a039\u201342 (2007)"},{"key":"173_CR27","doi-asserted-by":"crossref","unstructured":"Klein, O., Veltkamp, R.C.: Approximation algorithms for computing the earth mover\u2019s distance under transformations. In: Proccedings of the 16th International Symposium on Algorithms and Computation (ISAAC\u201905), pp.\u00a01019\u20131028 (2005)","DOI":"10.1007\/11602613_101"},{"issue":"2","key":"173_CR28","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1023\/A:1026543900054","volume":"40","author":"Y Rubner","year":"2000","unstructured":"Rubner, Y., Tomasi, C., Guibas, L.J.: The earth mover\u2019s distance as a metric for image retrieval. Int. J. Comput. Vis. 40(2), 99\u2013121 (2000)","journal-title":"Int. J. Comput. Vis."},{"key":"173_CR29","doi-asserted-by":"crossref","unstructured":"Sharathkumar, R., Agarwal, P. K.: Algorithms for the transportation problem in geometric settings. In: Proccedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA \u201912), pp.\u00a0306\u2013317 (2012)","DOI":"10.1137\/1.9781611973099.29"},{"key":"173_CR30","unstructured":"Typke, R., Giannopoulos, P., Veltkamp, R.C., Wierking, F., Oostrum, R.: Using transportation distances for measuring melodic similarity. In: Proccedings of the 4th International Conference Music Information Retrieval, pp.\u00a0107\u2013114 (2003)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0173-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0173-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0173-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0173-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T21:20:31Z","timestamp":1748985631000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0173-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,10]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["173"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0173-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,6,10]]},"assertion":[{"value":"7 July 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 June 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}