Showing a set is convex I'm stuck on showing that the following set is convex.
$$\{x:\|x-x_0\|_2\leq \|x-y\|_2 \text{ for all } y\in S\},$$
where $S\subset \mathbb{R}^n$.
$\|x-x_0\|_2\leq \|x-y\|_2$ implies $(x_0-y)^Tx\geq 0$, which a half-space. Therefore, this set is equivalent to the intersection of half-spaces:
$$\bigcap_{y\in S}\{x:(x_0-y)^Tx\geq 0\}.$$
It's not clear to me why $\|x-x_0\|_2\leq \|x-y\|_2$ implies $(x_0-y)^Tx\geq 0$. 
As $\|x-x_0\|_2\leq \|x-y\|_2$, we get $(x-x_0)^T(x-x_0)\leq (x-y)^T(x-y)$. Hence, $$x^Tx-x^Tx_0-x_0^Tx+x_0^Tx_0\leq x^Tx-x^Ty-y^Tx+y^Ty$$
I guess I'm allowed to say that $x^Tx_0=x_0^Tx$. Therefore, 
$$x^T_0x_0\leq 2x^T(x_0-y)+y^Ty$$ 
But I don't know how I can prove $(x_0-y)^Tx\geq 0$. 

Edit: Now that the question has been revised to ask about a different set, I'll give a different answer.  Note that for a given vector $y$,
\begin{align}
& \| x - x_0 \|_2 \leq \| x - y \|_2 \\
\iff & \| x - x_0 \|_2^2 \leq \| x - y \|_2^2 \\
\iff &  \| x \|_2^2 - 2 \langle x, x_0 \rangle + \| x_0 \|_2^2 \leq \| x \|_2^2 - 2 \langle x, y \rangle + \| y \|_2^2 \\
\iff & \langle x, 2(y - x_0) \rangle \leq \| y \|_2^2 - \|x_0 \|_2^2.
\end{align}
This shows that your set is an intersection of half spaces, so it's convex.
This agrees with the work you showed, which is correct.  The only incorrect thing is the statement that $\| x - x_0 \|_2 \leq \| x - y \|_2$ implies $\langle x_0 - y, x \rangle \geq 0$.  

Original answer:
For a given value of $y$, $\{ x: \| x-x_0\|_2 \leq \|y-x_0\|_2\}$ is a ball, hence it is convex.
Your set is an intersection of convex sets, so it is convex. No need to think about half spaces.
