Search

We show how auction algorithms, originally developed for the assignment problem, can be utilized in Merriman, Bence, and Osher's threshold dynamics scheme to simulate multi-phase motion by mean curvature in the presence of equality and inequality volume constraints on the individual phases. The resulting algorithms are highly efficient and robust, and can be used in simulations ranging from minimal partition problems in Euclidean space to semi-supervised machine learning via clustering on graphs. In the case of the latter application, numerous experimental results on benchmark machine learning datasets show that our approach exceeds the performance of current state-of-the-art methods, while requiring a fraction of the computation time.

We show how to construct a convolution kernel that has a desired anisotropic surface tension and desired anisotropic mobility to be used in threshold dynamics schemes for simulating weighted motion by mean curvature of interfaces, including networks of them, in both two and three dimensions. Moreover, we discuss necessary and sufficient conditions for the positivity of the kernel which, in the case of two-phase flow, ensures that the resulting scheme respects a comparison principle and implies convergence to the viscosity solution of the level set formulation of the flow. In particular, we show, in a barrier-type statement, that the kernel cannot possibly be positive unless both the mobility and the surface tension satisfy necessary conditions in three dimensions, and give a complete characterization. Among other results is a threshold dynamics scheme that is guaranteed to dissipate a non-local approximation to the interfacial energy in the fully anisotropic, multiphase setting, using the new kernel construction.