Numerical approximation of the Steiner problem in dimension 2 and 3

Bonnivard, Matthieu; Bretin, Elie; Lemenant, Antoine

doi:10.1090/mcom/3442

Numerical approximation of the Steiner problem in dimension $2$ and $3$
HTML articles powered by AMS MathViewer

by Matthieu Bonnivard, Elie Bretin and Antoine Lemenant HTML | PDF

Math. Comp. 89 (2020), 1-43 Request permission

Abstract:

The aim of this work is to present some numerical computations of solutions of the Steiner problem, based on the recent phase field approximations proposed by Lemenant and Santambrogio [C. R. Math. Acad. Sci. Paris 352 (2014), 451–454] and analyzed by Bonnivard, Lemenant, Millot, and Santambrogio. Our strategy consists in improving the regularity of the associated phase field solution by use of higher-order derivatives in the Cahn-Hilliard functional as in [Burger, Esposito, and Zeppieri, Multiscale Model Simul. 13 (2015), 1354–1389]. We justify the convergence of this slightly modified version of the functional, together with other techniques that we employ to improve the numerical experiments. In particular, we are able to consider a large number of points in dimension 2. We finally present and justify an approximation method that is efficient in dimension 3, which is one of the major novelties of the paper.

References

M. Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables, Dover Publications, Incorporated, 1974.
S. M. Allen and J. W. Cahn, A microscopic theory for antiphase boundary motion and its application to antiphase domain coarsening, Acta Metall. 27 (1979), 1085–1095.
Luigi Ambrosio and V. M. Tortorelli, On the approximation of free discontinuity problems, Boll. Un. Mat. Ital. B (7) 6 (1992), no. 1, 105–123 (English, with Italian summary). MR 1164940, DOI 10.1016/0012-365x(91)90062-7
F. Benmansour, G. Carlier, G. Peyré, and F. Santambrogio, Derivatives with respect to metrics and applications: subgradient marching algorithm, Numer. Math. 116 (2010), no. 3, 357–381. MR 2684290, DOI 10.1007/s00211-010-0305-8
Mauro Bonafini, Giandomenico Orlandi, and Édouard Oudet, Variational approximation of functionals defined on 1-dimensional connected sets: the planar case, SIAM J. Math. Anal. 50 (2018), no. 6, 6307–6332. MR 3890784, DOI 10.1137/17M1159452
Matthieu Bonnivard, Antoine Lemenant, and Vincent Millot, On a phase field approximation of the planar Steiner problem: existence, regularity, and asymptotic of minimizers, Interfaces Free Bound. 20 (2018), no. 1, 69–106. MR 3800751, DOI 10.4171/IFB/397
Matthieu Bonnivard, Antoine Lemenant, and Filippo Santambrogio, Approximation of length minimization problems among compact connected sets, SIAM J. Math. Anal. 47 (2015), no. 2, 1489–1529. MR 3337998, DOI 10.1137/14096061X
M. Burger, T. Esposito, and C. I. Zeppieri, Second-order edge-penalization in the Ambrosio-Tortorelli functional, Multiscale Model. Simul. 13 (2015), no. 4, 1354–1389. MR 3429728, DOI 10.1137/15M1020848
A. Chambolle, L. Ferrari, and B. Merlet, A phase-field approximation of the Steiner problem in dimension two, Adv. Calc. Var., to appear.
A. Chambolle, L. Ferrari, and B. Merlet, Variational approximation of size-mass energies for k-dimensional currents, ESAIM: Control, Optimisation and Calculus of Variations, to appear.
L. Q. Chen and J. Shen, Applications of semi-implicit Fourier-spectral method to phase field equations, Computer Physics Communications 108 (1998), 147–158.
Xinfu Chen, Generation and propagation of interfaces for reaction-diffusion equations, J. Differential Equations 96 (1992), no. 1, 116–141. MR 1153311, DOI 10.1016/0022-0396(92)90146-E
Vinícius Leal do Forte, Flávio Marcelo Tavares Montenegro, José André de Moura Brito, and Nelson Maculan, Iterated local search algorithms for the Euclidean Steiner tree problem in $n$ dimensions, Int. Trans. Oper. Res. 23 (2016), no. 6, 1185–1199. MR 3532536, DOI 10.1111/itor.12168
D. Eyre, Computational and Mathematical Models of Microstructural Evolution, Warrendale:The Material Research Society, 1998.
Irene Fonseca and Carlo Mantegazza, Second order singular perturbation models for phase transitions, SIAM J. Math. Anal. 31 (2000), no. 5, 1121–1143. MR 1759200, DOI 10.1137/S0036141099356830
Richard M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) Plenum, New York, 1972, pp. 85–103. MR 0378476
Antoine Lemenant and Filippo Santambrogio, A Modica-Mortola approximation for the Steiner problem, C. R. Math. Acad. Sci. Paris 352 (2014), no. 5, 451–454 (English, with English and French summaries). MR 3194255, DOI 10.1016/j.crma.2014.03.008
Luciano Modica and Stefano Mortola, Il limite nella $\Gamma$-convergenza di una famiglia di funzionali ellittici, Boll. Un. Mat. Ital. A (5) 14 (1977), no. 3, 526–529 (Italian, with English summary). MR 473971
Emanuele Paolini and Eugene Stepanov, Existence and regularity results for the Steiner problem, Calc. Var. Partial Differential Equations 46 (2013), no. 3-4, 837–860. MR 3018174, DOI 10.1007/s00526-012-0505-4
J. A. Sethian, Fast marching methods, SIAM Rev. 41 (1999), no. 2, 199–235. MR 1684542, DOI 10.1137/S0036144598347059
J. A. Sethian, Level set methods and fast marching methods, 2nd ed., Cambridge Monographs on Applied and Computational Mathematics, vol. 3, Cambridge University Press, Cambridge, 1999. Evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science. MR 1700751
Jie Shen, Cheng Wang, Xiaoming Wang, and Steven M. Wise, Second-order convex splitting schemes for gradient flows with Ehrlich-Schwoebel type energy: application to thin film epitaxy, SIAM J. Numer. Anal. 50 (2012), no. 1, 105–125. MR 2888306, DOI 10.1137/110822839