  The geometric transportation problem takes as input a set of points $P$ in
$d$-dimensional Euclidean space and a supply function $\mu : P \to \mathbb{R}$.
The goal is to find a transportation map, a non-negative assignment $\tau : P
\times P \to \mathbb{R}_{\geq 0}$ to pairs of points, so the total assignment
leaving each point is equal to its supply, i.e., $\sum_{r \in P} \tau(q, r) -
\sum_{p \in P} \tau(p, q) = \mu(q)$ for all points $q \in P$. The goal is to
minimize the weighted sum of Euclidean distances for the pairs, $\sum_{(p, q)
\in P \times P} \tau(p, q) \cdot ||q - p||_2$.
  We describe the first algorithm for this problem that returns, with high
probability, a $(1 + \varepsilon)$-approximation to the optimal transportation
map in $n\varepsilon^{-O(d)}\log^{O(d)}{n}$ time. In contrast to the previous
best algorithms for this problem, our near-linear running time bound is
independent of the spread of $P$ and the magnitude of its real-valued supplies.
