How to show $f(z) = \sum_{j=1}^m \min_{\ell = 1, \cdots, q}\| x^j - z^\ell \|$ is NOT convex on $\mathbb{R}^n \times \cdots \times \mathbb{R}^n$
Let $Z\in\mathbb R^n$ be a point such that $\|x^j-Z\|,\|x^j-2Z\|>\|x^j\|$ for each $j,$ for example $Z=(1+2\max_j\|x^j\|,0,0,\dots,0).$ Then
$$f(0,2Z,2Z,\dots,2Z)=\sum_{j=1}^m\|x^j\|$$ and $$f(2Z,0,0,\dots,0)=\sum_{j=1}^m\|x^j\|$$ but $$f(Z,Z,Z,\dots,Z)>\sum_{j=1}^m\|x^j\|$$ which contradicts midpoint convexity of $f.$
I came to this argument by first considering the case where all the $x^j$ are equal, then generalizing.