No abstract uploaded!

No abstract uploaded!

No abstract uploaded!

The optimal mass transportation problem, proposed by Monge, is dominated by the Monge-Ampere equation. In general, as the Monge-Ampere equation is highly non-linear, this type of partial dierential equations is beyond the solving ability of a conventional nite element method. This diculty led Gu et al. alternatively to the discrete optimal mass transportation problem. They developed variational principles for this problem and reported the calculation for the optimal mapping, based on theorem that among all possible cell decompositions, with constrained measures, the trans- portation cost of the discrete mapping from cells to the corresponding discrete points is minimized by the decomposition induced by a power Voronoi diagram. Their research inspired us to consider a similar discrete optimal mass transportation problem. Here we replace the L2 Euclidean distance by the length of the shortest path connecting two points on a line network. To solve the optimal trans- portation problem on a line network, we study a type of Voronoi diagram on undirected and connected networks and propose an elegant construction algorithm. We further consider weighted distances in a network and develop a method to compute the centroidal Voronoi tessellation (CVT) for a network. By using real geographic data, the method proposed is proved ecient and eective in several practical applications, including charging station distribution in a trac network, and trash can distribution in a park.

Computing centroidal Voronoi tessellations (CVT) has many applications in computer graphics. The existing methods, such as the Lloyd algorithm and the quasi-Newton solver, are efficient and easy to implement; however, they compute only the local optimal solutions due to the highly non-linear nature of the CVT energy. This paper presents a novel method, called manifold differential evolution (MDE), for computing globally optimal geodesic CVT energy on triangle meshes. Formulating the mutation operator using discrete geodesics, MDE naturally extends the powerful differential evolution framework from Euclidean spaces to manifold domains. Under mild assumptions, we show that MDE has a provable probabilistic convergence to the global optimum. Experiments on a wide range of 3D models show that MDE consistently outperforms the existing methods by producing results with lower energy. Thanks to its intrinsic and global nature, MDE is insensitive to initialization and mesh tessellation. Moreover, it is able to handle multiply-connected Voronoi cells, which are challenging to the existing geodesic CVT methods.