Phase field approximation of the Steiner tree problem
The Steiner problem is one of the simplest length minimization problem to formulate. It consists in finding the shortest path connecting a given, finite set of points in the plane.
Relying on a famous result by Modica and Mortola, we have proposed in collaboration with A. Lemenant and F. Santambrogio a variational approximation for this problem. One major difficulty of such approximation is to enforce the connectedness of the optimal paths. Our strategy relies on the penalization of disconnected paths using geodesic distances associated to a metric related to the phase field itself.
We have then introduced with A. Lemenant and V. Millot a relaxed energy based on the dissociation of the phase field and the geodesics, allowing for a more flexible and efficient numerical approximation of the minimizers using a splitting approach.
We have refined the previous energy and studied the properties of its numerical approximation in a joint work with E. Bretin and A. Lemenant. We show below some examples of simulations in 2d and 3d.
For every setting, we start by plotting the phase field function minimizing the energy associated with a relatively high value of the regularization parameter epsilon. Then, starting from this minimizer, we diminish epsilon and compute a new local minimum, and repeat the operation multiple times. Last picture corresponds to the final local minimizer that we obtain.
The numerical solution of the Steiner problem is then given by the zero level set of the last phase field function, that is, the region in black in the 2d pictures, and in green in the 3d pictures.
