{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T20:01:45Z","timestamp":1777492905539,"version":"3.51.4"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T00:00:00Z","timestamp":1723680000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T00:00:00Z","timestamp":1723680000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Numer Algor"],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s11075-024-01903-y","type":"journal-article","created":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T03:26:51Z","timestamp":1723692411000},"page":"949-1004","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Solving semi-discrete optimal transport problems: star shapedeness and Newton\u2019s method"],"prefix":"10.1007","volume":"99","author":[{"given":"Luca","family":"Dieci","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniyar","family":"Omarov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,15]]},"reference":[{"key":"1903_CR1","first-page":"1","volume-title":"Lecture Notes on Optimal Transport Problems","author":"L Ambrosio","year":"2003","unstructured":"Ambrosio, L.: Lecture Notes on Optimal Transport Problems, pp. 1\u201352. Springer, Berlin Heidelberg, Berlin, Heidelberg (2003)"},{"issue":"1","key":"1903_CR2","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1137\/0216006","volume":"16","author":"F Aurenhammer","year":"1987","unstructured":"Aurenhammer, F.: Power diagrams: Properties, algorithms and applications. SIAM J. Comput. 16(1), 78\u201396 (1987)","journal-title":"SIAM J. Comput."},{"key":"1903_CR3","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-030-86695-2_3","volume":"I","author":"V Balestro","year":"2022","unstructured":"Balestro, V., Martini, H.: Minkowski geometry\u2014some concepts and recent developments. Surv. Geom. I, 49\u201395 (2022)","journal-title":"Surv. Geom."},{"key":"1903_CR4","doi-asserted-by":"crossref","unstructured":"Benamou, J.-D., Brenier, Y.: A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numerische Mathematik, 84(3), 375\u2013393, (2000)","DOI":"10.1007\/s002110050002"},{"key":"1903_CR5","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.jcp.2013.12.015","volume":"260","author":"J-D Benamou","year":"2014","unstructured":"Benamou, J.-D., Froese, B.D., Oberman, A.M.: Numerical solution of the optimal transportation problem using the Monge-Amp\u00e8re equation. J. Comput. Phys. 260, 107\u2013126 (2014)","journal-title":"J. Comput. Phys."},{"key":"1903_CR6","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B.: Linear Analysis, Cambridge Mathematical Textbooks, p. 21 Cambridge University Press, (1999)","DOI":"10.1017\/CBO9781139168472"},{"key":"1903_CR7","doi-asserted-by":"crossref","unstructured":"Bounceur, A., Bezoui, M., Euler, R.: Boundaries and hulls of Euclidean graphs: From theory to practice, CRC Press, p. 34 (2018)","DOI":"10.1201\/9781315169897"},{"issue":"6","key":"1903_CR8","doi-asserted-by":"publisher","first-page":"2545","DOI":"10.1137\/141000993","volume":"53","author":"DP Bourne","year":"2015","unstructured":"Bourne, D.P., Roper, S.M.: Centroidal power diagrams, Lloyd\u2019s algorithm, and applications to optimal location problems. SIAM J. Numer. Anal. 53(6), 2545\u20132569 (2015)","journal-title":"SIAM J. Numer. Anal."},{"key":"1903_CR9","unstructured":"Bourne, D.P., Schmitzer, B., Wirth, B.: Semi-discrete unbalanced optimal transport and quantization. arXiv: Optimization and Control, 2018-08"},{"issue":"2","key":"1903_CR10","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/0167-7152(93)90159-G","volume":"16","author":"JA Cuesta-Albertos","year":"1993","unstructured":"Cuesta-Albertos, J.A., Tuero-D\u00edaz, A.: A characterization for the solution of the Monge-Kantorovich mass transference problem. Stat. Probab. Lett. 16(2), 147\u2013152 (1993)","journal-title":"Stat. Probab. Lett."},{"key":"1903_CR11","unstructured":"Cuturi, M.: Sinkhorn distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems, Curran Associates, Inc., vol. 26, pp. 2292\u20132300 (2013)"},{"key":"1903_CR12","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s00211-018-1000-4","volume":"141","author":"F De Gournay","year":"2019","unstructured":"De Gournay, F., Kahn, J., Lebrat, L.: Differentiation and regularity of semi-discrete optimal transport with respect to the parameters of the discrete measure. Numer. Math. 141, 429\u2013453 (2019)","journal-title":"Numer. Math."},{"key":"1903_CR13","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1016\/j.camwa.2023.06.036","volume":"146","author":"L Dieci","year":"2023","unstructured":"Dieci, L., Omarov, D.: Techniques for continuous optimal transport problem. Comput. Math. Appl. 146, 176\u2013191 (2023)","journal-title":"Comput. Math. Appl."},{"key":"1903_CR14","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1016\/j.cam.2018.12.034","volume":"353","author":"L Dieci","year":"2019","unstructured":"Dieci, L., Walsh, J.D., III.: The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation. J. Comput. Appl. Math. 353, 318\u2013344 (2019)","journal-title":"J. Comput. Appl. Math."},{"key":"1903_CR15","unstructured":"Dobrin, A.: A review of properties and variations of Voronoi diagrams. Whitman College. (2005)"},{"issue":"4","key":"1903_CR16","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1137\/S0036144599352836","volume":"41","author":"Q Du","year":"1999","unstructured":"Du, Q., Faber, V., Gunzburger, M.: Centroidal Voronoi tessellations: Applications and algorithms. SIAM Rev. 41(4), 637\u2013676 (1999)","journal-title":"SIAM Rev."},{"key":"1903_CR17","first-page":"313","volume":"86","author":"S Fortune","year":"1986","unstructured":"Fortune, S.: A sweepline algorithm for Voronoi diagrams. Proc. Second Ann. Symp. Comput. Geom. SCG New York, ACM. 86, 313\u2013322 (1986)","journal-title":"Proc. Second Ann. Symp. Comput. Geom. SCG New York, ACM."},{"issue":"3","key":"1903_CR18","doi-asserted-by":"publisher","first-page":"A1432","DOI":"10.1137\/110822372","volume":"34","author":"BD Froese","year":"2012","unstructured":"Froese, B.D.: A numerical method for the elliptic Monge-Amp\u00e8re equation with transport boundary conditions. SIAM J Sci. Comput. 34(3), A1432\u2013A1459 (2012)","journal-title":"SIAM J Sci. Comput."},{"issue":"2","key":"1903_CR19","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/BF02392620","volume":"177","author":"W Gangbo","year":"1996","unstructured":"Gangbo, W., McCann, R.J.: The geometry of optimal transportation. Acta Math. 177(2), 113\u2013161 (1996)","journal-title":"Acta Math."},{"key":"1903_CR20","first-page":"817","volume-title":"Comput. Sci. Its Appl. \u2013 ICCSA 2003","author":"J Gao","year":"2003","unstructured":"Gao, J., Gupta, R.: Efficient proximity search for 3-D cuboids. In: Kumar, Vipin, Gavrilova, Marina L., Tan, Chih Jeng Kenneth., L\u2019Ecuyer, Pierre (eds.) Comput. Sci. Its Appl. \u2013 ICCSA 2003, pp. 817\u2013826. Berlin Heidelberg, Berlin, Heidelberg, Springer (2003)"},{"key":"1903_CR21","doi-asserted-by":"crossref","unstructured":"Gei\u00df, D., Klein, R., Penninger, R., Rote, G.: Optimally solving a transportation problem using Voronoi diagrams. Comput. Geom. 46(8), 1009\u20131016 (2013)","DOI":"10.1016\/j.comgeo.2013.05.005"},{"key":"1903_CR22","first-page":"279","volume":"207","author":"C Godsil","year":"2001","unstructured":"Godsil, C., Royle, G.F.: Algebraic Graph Theory, Springer Science & Business. Media 207, 279 (2001)","journal-title":"Media"},{"key":"1903_CR23","doi-asserted-by":"crossref","unstructured":"Gro\u00df, C. and Strempel, T.-K.: On generalizations of conics and on a generalization of the Fermat-Torricelli problem. The American mathematical monthly, 105(8), 732\u2013743 (1998)","DOI":"10.1080\/00029890.1998.12004955"},{"key":"1903_CR24","doi-asserted-by":"crossref","unstructured":"Hartmann, V.N., Schuhmacher, D.: Semi-discrete optimal transport: a solution procedure for the unsquared Euclidean distance case. Mathematical Methods of Operations Research, pp. 1\u201331, (2020)","DOI":"10.1007\/s00186-020-00703-z"},{"key":"1903_CR25","unstructured":"Jahn, T.: An invitation to generalized Minkowski geometry. (2019)"},{"key":"1903_CR26","unstructured":"Kantorovich, L.V.: On the translocation of masses. C.R. (Doklady) Acad. Sci. URSS (N.S.), 37, 199\u2013201 (1942)"},{"key":"1903_CR27","first-page":"225","volume":"3","author":"LV Kantorovich","year":"1948","unstructured":"Kantorovich, L.V.: On a problem of Monge. Usp. Mat. Nauk 3, 225\u2013226 (1948)","journal-title":"Usp. Mat. Nauk"},{"key":"1903_CR28","volume-title":"Numer. methods bifurcation probl.","author":"HB Keller","year":"1987","unstructured":"Keller, H.B.: Numer. methods bifurcation probl., vol. Tata. Institute of Fundamental Research. Springer-Verlag, Bombay (1987)"},{"issue":"9","key":"1903_CR29","doi-asserted-by":"publisher","first-page":"2603","DOI":"10.4171\/jems\/889","volume":"21","author":"J Kitagawa","year":"2019","unstructured":"Kitagawa, J., M\u00e9rigot, Q., Thibert, B.: Convergence of a Newton algorithm for semi-discrete optimal transport. J. Eur. Math. Soc. 21(9), 2603\u20132651 (2019)","journal-title":"J. Eur. Math. Soc."},{"key":"1903_CR30","doi-asserted-by":"crossref","unstructured":"L\u00e9vy, B.: A numerical algorithm for $$L_2$$ semi-discrete optimal transport in 3D. ESAIM: Mathematical Modelling and Numerical Analysis, 49(6), 1693\u20131715 (2015)","DOI":"10.1051\/m2an\/2015055"},{"key":"1903_CR31","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.cag.2018.01.009","volume":"72","author":"B L\u00e9vy","year":"2018","unstructured":"L\u00e9vy, B., Schwindt, E.L.: Notions of optimal transport theory and how to implement them on a computer. Comput. Graph. 72, 135\u2013148 (2018)","journal-title":"Comput. Graph."},{"key":"1903_CR32","doi-asserted-by":"crossref","unstructured":"M\u00e9rigot, Q.: A comparison of two dual methods for discrete optimal transport. In Frank Nielsen and Fr\u00e9d\u00e9ric Barbaresco, editors, GSI 2013 \u2014 Geometric Science of Information, Aug 2013, Paris, France, of Lecture Notes in Computer Science, Springer, vol. 8085 pp. 389\u2013396 (1781)","DOI":"10.1007\/978-3-642-40020-9_42"},{"key":"1903_CR33","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.cad.2019.05.037","volume":"115","author":"J Meyron","year":"2019","unstructured":"Meyron, J.: Initialization procedures for Discrete and semi-discrete optimal transport. Comput. Aided. Des. 115, 13\u201322 (2019)","journal-title":"Comput. Aided. Des."},{"key":"1903_CR34","unstructured":"Monge, G.: M\u00e9moire sur la th\u00e9orie des d\u00e9blais et des remblais. In Histoire de l\u2019Acad\u00e9mie Royale des Sciences de Paris, avec les M\u00e9moires de Math\u00e9matique et de Physique pour la m\u00eame ann\u00e9e, Acad\u00e9mie des sciences (France)., In French. pp. 666\u2013704 (1781)"},{"key":"1903_CR35","doi-asserted-by":"crossref","unstructured":"Peyr\u00e9, G., Cuturi, M.: Computational optimal transport: With applications to data science. Foundations and Trends\u00ae in Machine Learning, 11(5-6), 355\u2013607 (2019)","DOI":"10.1561\/2200000073"},{"key":"1903_CR36","doi-asserted-by":"crossref","unstructured":"Pratelli, A.: On the equality between Monge\u2019s infimum and Kantorovich\u2019s minimum in optimal mass transportation. Annales de l\u2019Institut Henri Poincare (B) Probability and Statistics, 43(1), 1\u201313 (2007)","DOI":"10.1016\/j.anihpb.2005.12.001"},{"issue":"3","key":"1903_CR37","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s001840000052","volume":"51","author":"L R\u00fcschendorf","year":"2000","unstructured":"R\u00fcschendorf, L., Uckelmann, L.: Numerical and analytical results for the transportation problem of Monge-Kantorovich. Metrika 51(3), 245\u2013258 (2000)","journal-title":"Metrika"},{"key":"1903_CR38","first-page":"94","volume":"55","author":"F Santambrogio","year":"2015","unstructured":"Santambrogio, F.: Optimal transport for applied mathematicians. Springer 55, 94 (2015)","journal-title":"Springer"},{"issue":"2","key":"1903_CR39","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1137\/0214034","volume":"14","author":"M Sharir","year":"1985","unstructured":"Sharir, M.: Intersection and closest-pair problems for a set of planar discs. SIAM J. Comput. 14(2), 448\u2013468 (1985)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1903_CR40","doi-asserted-by":"publisher","first-page":"402","DOI":"10.2307\/2314570","volume":"74","author":"R Sinkhorn","year":"1967","unstructured":"Sinkhorn, R.: Diagonal equivalence to matrices with prescribed row and column sums. Am. Math. Mon. 74(4), 402\u2013405 (1967)","journal-title":"Am. Math. Mon."},{"key":"1903_CR41","doi-asserted-by":"crossref","unstructured":"Solomon, J., Goes, F., Peyr\u00e9, G., Cuturi, M., Butscher, A., Nguyen, A., Du, T., Guibas, L.: Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains. ACM Transactions on Graphics, 34, 07 (2015)","DOI":"10.1145\/2766963"},{"key":"1903_CR42","series-title":"Graduate Studies in Mathematics","doi-asserted-by":"crossref","DOI":"10.1090\/gsm\/058","volume-title":"Topics in Optimal Transportation","author":"C Villani","year":"2003","unstructured":"Villani, C.: Topics in Optimal Transportation. Graduate Studies in Mathematics, vol. 58. American Mathematical Society, Providence, R.I. (2003)"}],"container-title":["Numerical Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-024-01903-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11075-024-01903-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-024-01903-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,10]],"date-time":"2025-05-10T07:51:24Z","timestamp":1746863484000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11075-024-01903-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,15]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["1903"],"URL":"https:\/\/doi.org\/10.1007\/s11075-024-01903-y","relation":{},"ISSN":["1017-1398","1572-9265"],"issn-type":[{"value":"1017-1398","type":"print"},{"value":"1572-9265","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,15]]},"assertion":[{"value":"22 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}