{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T03:38:22Z","timestamp":1764905902444,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-18-1-0502","FA9550-18-1-0167"],"award-info":[{"award-number":["FA9550-18-1-0502","FA9550-18-1-0167"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["Simons-CRM scholar-in-residence"],"award-info":[{"award-number":["Simons-CRM scholar-in-residence"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-18-1-2527"],"award-info":[{"award-number":["N00014-18-1-2527"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sci Comput"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1007\/s10915-020-01143-x","type":"journal-article","created":{"date-parts":[[2020,2,10]],"date-time":"2020-02-10T15:02:34Z","timestamp":1581346954000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["No-Collision Transportation Maps"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6227-0941","authenticated-orcid":false,"given":"Levon","family":"Nurbekyan","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Iannantuono","sequence":"additional","affiliation":[]},{"given":"Adam M.","family":"Oberman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,10]]},"reference":[{"key":"1143_CR1","unstructured":"Altschuler, J., Bach, F., Rudi, A., Weed, J.: Approximating the quadratic transportation metric in near-linear time. arXiv preprint arXiv:1810.10046 (2018)"},{"key":"1143_CR2","unstructured":"Altschuler, J., Weed, J., Rigollet, P.: Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. In: Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS\u201917, pp. 1961\u20131971. Curran Associates Inc., USA (2017). http:\/\/dl.acm.org\/citation.cfm?id=3294771.3294958. Accessed Dec 14 2019"},{"key":"1143_CR3","volume-title":"Gradient Flows in Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics ETH Z\u00fcrich","author":"L Ambrosio","year":"2008","unstructured":"Ambrosio, L., Gigli, N., Savar\u00e9, G.: Gradient Flows in Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics ETH Z\u00fcrich, 2nd edn. Birkh\u00e4user Verlag, Basel (2008)","edition":"2"},{"issue":"4","key":"1143_CR4","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci. 7(4), 448\u2013461 (1973). https:\/\/doi.org\/10.1016\/S0022-0000(73)80033-9","journal-title":"J. Comput. Syst. Sci."},{"key":"1143_CR5","unstructured":"Cuturi, M.: Sinkhorn distances: lightspeed computation of optimal transport. In: Burges, C.J.C., Bottou, L., Welling, M., Ghahramani, Z., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems, pp. 2292\u20132300. Curran Associates, Inc. (2013). http:\/\/papers.nips.cc\/paper\/4927-sinkhorn-distances-lightspeed-computation-of-optimal-transport.pdf"},{"key":"1143_CR6","unstructured":"Cuturi, M., Doucet, A.: Fast computation of Wasserstein barycenters. In: Xing, E.P., Jebara, T. (eds.) Proceedings of the 31st International Conference on Machine Learning, Proceedings of Machine Learning Research, vol.\u00a032, pp. 685\u2013693. PMLR, Bejing, China (2014). http:\/\/proceedings.mlr.press\/v32\/cuturi14.html. Accessed Dec 14 2019"},{"key":"1143_CR7","doi-asserted-by":"crossref","unstructured":"Dasgupta, S., Freund, Y.: Random projection trees and low dimensional manifolds. Citeseer (2008)","DOI":"10.1145\/1374376.1374452"},{"key":"1143_CR8","unstructured":"Dasgupta, S., Sinha, K.: Randomized partition trees for exact nearest neighbor search. In: Conference on Learning Theory, pp. 317\u2013337 (2013)"},{"key":"1143_CR9","unstructured":"Flamary, R., Courty, N.: POT Python optimal transport library (2017). https:\/\/github.com\/rflamary\/POT. Accessed Dec 14 2019"},{"key":"1143_CR10","unstructured":"Genevay, A., Cuturi, M., Peyr\u00e9, G., Bach, F.: Stochastic optimization for large-scale optimal transport. In: Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS\u201916, pp. 3440\u20133448. Curran Associates Inc., USA (2016). http:\/\/dl.acm.org\/citation.cfm?id=3157382.3157482. Accessed Dec 14 2019"},{"key":"1143_CR11","doi-asserted-by":"publisher","unstructured":"Indyk, P.: Algorithms for dynamic geometric problems over data streams. In: Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, STOC \u201904, pp. 373\u2013380. ACM, New York (2004). https:\/\/doi.org\/10.1145\/1007352.1007413","DOI":"10.1145\/1007352.1007413"},{"key":"1143_CR12","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Nearest neighbors in high-dimensional spaces. In: Handbook of Discrete and Computational Geometry. Citeseer (2004)","DOI":"10.1201\/9781420035315.ch39"},{"key":"1143_CR13","unstructured":"Indyk, P.: A near linear time constant factor approximation for Euclidean bichromatic matching (cost). In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201907, pp. 39\u201342. Society for Industrial and Applied Mathematics, Philadelphia (2007). http:\/\/dl.acm.org\/citation.cfm?id=1283383.1283388. Accessed Dec 14 2019"},{"key":"1143_CR14","unstructured":"Indyk, P., Thaper, N.: Fast image retrieval via embeddings. In: Proceedings of the 3rd International Workshop on Statistical and Computational Theories of Vision, vol. 2, no. 3, p. 5. (2003)"},{"key":"1143_CR15","unstructured":"Jacobs, M., L\u00e9ger, F.: A fast approach to optimal transport: the back-and-forth method. Preprint (2019). ArXiv:1905.12154 [math.OC]"},{"key":"1143_CR16","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2019.2921572","author":"J Johnson","year":"2019","unstructured":"Johnson, J., Douze, M., J\u00e9gou, H.: Billion-scale similarity search with GPUs. IEEE Trans. Big Data (2019). https:\/\/doi.org\/10.1109\/TBDATA.2019.2921572","journal-title":"IEEE Trans. Big Data"},{"key":"1143_CR17","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1307\/mmj\/1028990175","volume":"4","author":"H Knothe","year":"1957","unstructured":"Knothe, H.: Contributions to the theory of convex bodies. Mich. Math. J. 4, 39\u201352 (1957)","journal-title":"Mich. Math. J."},{"key":"1143_CR18","unstructured":"Li, K., Malik, J.: Fast k-nearest neighbour search via prioritized DCI. In: Proceedings of the 34th International Conference on Machine Learning, vol. 70, pp. 2081\u20132090. JMLR.org (2017)"},{"issue":"8","key":"1143_CR19","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1002\/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#","volume":"27","author":"DR Musser","year":"1997","unstructured":"Musser, D.R.: Introspective sorting and selection algorithms. Softw. Pract. Exp. 27(8), 983\u2013993 (1997)","journal-title":"Softw. Pract. Exp."},{"key":"1143_CR20","unstructured":"Peyr\u00e9, G., Cuturi, M.: Computational Optimal Transport: With Applications to Data Science. Now (2019). https:\/\/ieeexplore.ieee.org\/document\/8641476. Accessed Dec 14 2019"},{"issue":"12","key":"1143_CR21","doi-asserted-by":"publisher","first-page":"1610","DOI":"10.1109\/83.544569","volume":"5","author":"H Radha","year":"1996","unstructured":"Radha, H., Vetterli, M., Leonardi, R.: Image compression using binary space partitioning trees. IEEE Trans. Image Process. 5(12), 1610\u20131624 (1996). https:\/\/doi.org\/10.1109\/83.544569","journal-title":"IEEE Trans. Image Process."},{"key":"1143_CR22","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1214\/aoms\/1177729394","volume":"23","author":"M Rosenblatt","year":"1952","unstructured":"Rosenblatt, M.: Remarks on a multivariate transformation. Ann. Math. Stat. 23, 470\u2013472 (1952). https:\/\/doi.org\/10.1214\/aoms\/1177729394","journal-title":"Ann. Math. Stat."},{"issue":"3","key":"1143_CR23","doi-asserted-by":"publisher","first-page":"A1443","DOI":"10.1137\/16M1106018","volume":"41","author":"B Schmitzer","year":"2019","unstructured":"Schmitzer, B.: Stabilized sparse scaling algorithms for entropy regularized transport problems. SIAM J. Sci. Comput. 41(3), A1443\u2013A1481 (2019)","journal-title":"SIAM J. Sci. Comput."},{"key":"1143_CR24","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer, Berlin (2003)"},{"key":"1143_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/b12016","volume-title":"Topics in Optimal Transportation. Graduate Studies in Mathematics","author":"C Villani","year":"2003","unstructured":"Villani, C.: Topics in Optimal Transportation. Graduate Studies in Mathematics, vol. 58. American Mathematical Society, Providence (2003). https:\/\/doi.org\/10.1007\/b12016"},{"key":"1143_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71050-9","volume-title":"Optimal Transport, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]","author":"C Villani","year":"2009","unstructured":"Villani, C.: Optimal Transport, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 338. Springer, Berlin (2009). https:\/\/doi.org\/10.1007\/978-3-540-71050-9"},{"issue":"6","key":"1143_CR27","doi-asserted-by":"publisher","first-page":"1755","DOI":"10.1109\/18.165448","volume":"38","author":"X Wu","year":"1992","unstructured":"Wu, X.: Image coding by adaptive tree-structured segmentation. IEEE Trans. Inf. Theory 38(6), 1755\u20131767 (1992). https:\/\/doi.org\/10.1109\/18.165448","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Journal of Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10915-020-01143-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10915-020-01143-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10915-020-01143-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T23:58:01Z","timestamp":1612915081000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10915-020-01143-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["1143"],"URL":"https:\/\/doi.org\/10.1007\/s10915-020-01143-x","relation":{},"ISSN":["0885-7474","1573-7691"],"issn-type":[{"type":"print","value":"0885-7474"},{"type":"electronic","value":"1573-7691"}],"subject":[],"published":{"date-parts":[[2020,2]]},"assertion":[{"value":"14 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"45"}}