Let $S = \{x \in \mathbb{R}^n : || x - x_0 || \leq ||x-x_i|| , i=1,2...k \}$. This set is a Voronoi region. This set is a polyhedron, and therefore is necessarily convex. So there should be a convexity proof for it where if we let $x_a,x_b \in S$ we want:
$$||tx_a + (1-t)x_b - x_0 || \leq ||tx_a + (1-t)x_b - x_i||$$
for $0 \leq t \leq 1$. Giving this a try I have gotten this far:
$$ ||tx_a + (1-t)x_b - x_0 || $$ $$=||tx_a + x_b - tx_b - x_0||$$ $$\leq ||x_b - x_0|| + ||tx_a - tx_b||$$ $$\leq ||x_b - x_i|| + t ||x_a - x_b||$$
from here I am unsure how to proceed. How do I get to the final inequality?
For clarity, let ${v_i}_{i=1}^k$ denote the Voronoi sites and $x_a$ and $x_b$ be arbitrary points in a particular Voronoi cell associated with site $v_i$.
You can't apply the triangle inequality so aggressively and still get the estimate -- $||x_a-v_i||$ and $||x_b-v_i||$ can be large even if $||tx_a + (1-t)x_b-v_j||$ is relatively small so anything that runs into those earlier terms won't get the result.
First, establish an equivalent inequality to $||x-v_i||^2 \leq ||x-v_j||^2$ by exanding and rearranging terms,
\begin{align} ||x-v_i||^2 & \leq ||x-v_j||^2\\ ||x||^2 + ||v_i||^2 - 2x\cdot v_i & \leq ||x||^2 + ||v_j||^2 - 2x\cdot v_j\\ ||v_i||^2 - 2x\cdot v_i & \leq ||v_j||^2 - 2x\cdot v_j. \end{align}
Now we can proceed with the estimate for a point $y = tx_a + (1-t)x_b$: \begin{align} || y - v_i||^2 & = ||y||^2 + ||v_i||^2 - 2y\cdot v_i\\ & = ||y||^2 + ||v_i||^2 - 2\left(tx_a + (1-t)x_b \right)\cdot v_i\\ & = ||y||^2 + t(||v_i||^2 - 2x_a\cdot v_i)+ (1-t) (||v_i||^2 - 2x_b\cdot v_i). \end{align}
Now our earlier estimate applied to $x_a$ and $x_b$ which are both in the Voronoi cell of $v_i$ allowing us to replace $v_i$ with $v_j$, $$ || y - v_i||^2 \leq ||y||^2 + t(||v_j||^2 - 2x_a\dot v_i)+ (1-t) (||v_j||^2 - 2x_b\cdot v_i). $$
Finally, we can regroup the terms (applying the earlier equalities in reverse, \begin{align} || y - v_i||^2 & \leq ||y||^2 + t(||v_j||^2 - 2x_a\dot v_i)+ (1-t) (||v_j||^2 - 2x_b\cdot v_i)\\ & = ||y||^2 + ||v_j||^2 + 2(tx_a + (1-t)x_b)\cdot v_j\\ & = ||y - v_j||^2. \end{align}