This paper introduces a numerical algorithm to compute the $L_2$ optimal
transport map between two measures $\mu$ and $\nu$, where $\mu$ derives from a
density $\rho$ defined as a piecewise linear function (supported by a
tetrahedral mesh), and where $\nu$ is a sum of Dirac masses.
I first give an elementary presentation of some known results on optimal
transport and then observe a relation with another problem (optimal sampling).
This relation gives simple arguments to study the objective functions that
characterize both problems.
I then propose a practical algorithm to compute the optimal transport map
between a piecewise linear density and a sum of Dirac masses in 3D. In this
semi-discrete setting, Aurenhammer et.al [\emph{8th Symposium on Computational
Geometry conf. proc.}, ACM (1992)] showed that the optimal transport map is
determined by the weights of a power diagram. The optimal weights are computed
by minimizing a convex objective function with a quasi-Newton method. To
evaluate the value and gradient of this objective function, I propose an
efficient and robust algorithm, that computes at each iteration the
intersection between a power diagram and the tetrahedral mesh that defines the
measure $\mu$.
The numerical algorithm is experimented and evaluated on several datasets,
with up to hundred thousands tetrahedra and one million Dirac masses.

本文介绍了一种计算两个测度之间 L2 最优传输图的数值算法，其中一个测度源自由分段线性函数（由四面体网格支持）定义的密度 rho，而另一个测度则是 Dirac 质量之和。作者提出了一个实用的算法来计算分段线性密度与 Dirac 质量总和之间的最优传输图。