Voronoi diagram

Remarks

Example: for the two sites $p_1 = (-1, 0)$ and $p_2 = (1, 0)$ in $\R^2$, the condition $\norm{x - p_1} \le \norm{x - p_2}$ reduces to $x_1 \le 0$. So $V(p_1)$ is the closed half-plane $x_1 \le 0$, $V(p_2)$ is the half-plane $x_1 \ge 0$, and they meet along the perpendicular bisector $x_1 = 0$.

Non-example: the cells $\set{x : x_1 \le -1}$ and $\set{x : x_1 \ge -1}$ are not the Voronoi diagram of these two sites, since the point $(-1/2, 0)$ is closer to $p_1$ but lies in the second set only.

Each condition $\norm{x - p_i} \le \norm{x - p_j}$ defines a closed half-space, so each cell is a convex polyhedron. The cells cover $\R^n$, and two distinct cells have disjoint interiors, so the Voronoi diagram is a tiling of $\R^n$. The Voronoi cell of a point of a lattice, with all lattice points as sites, is a Voronoi cell in the sense of the geometry of numbers.