The computation can be improved by space partition tree for all convex distance functions including $L_2$. By using the mean of the points in each leaf, one can compute a lower bound for the sum of distances in $O(|I|)$ with $|I|$ the total number of leafs. This lower bound is based on the following simple inequality:
\begin{equation}
\sum_{x\in\Omega} d(x,y)\geq \sum_{i\in I} |\Omega_i| d(\bar{x}_i,y),
\end{equation}
where $\Omega$ is the point set, $\{\Omega_i\}_{i \in I}$ are the leafs of space partition, and $\bar{x}_i$ is the mean of the points in each leaf.
This inequality allows quickly removing points which cannot be the minimizer. The way of doing so is to pick a candidate point $x^*$ from $\Omega$ and compute the sum of distance $s^*=\sum_{x\in\Omega} d(x,x^*)$. Do space partition and compute the lower bound of sum of distances for the rest of the points. If a lower bound is greater than $s^*$, then we know the corresponding point cannot be the minimizer.
One can grow the tree adaptively and use this result to remove the points much as possible during different stages of comparison.