Convexity proof for Voronoi Polygon 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?
 A: 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}
