---
tag: ZQR56X168K
kind: definition
name: Voronoi cell
msc: [52C07, 11H06, 52C22]
defines: V1R1R88GV6
uses: [0NPPGHQNXQ, WN9V7WSJKF]
sources:
  - url: https://en.wikipedia.org/wiki/Voronoi_diagram
---

## Definition

Let $S \subset \R^n$ be a nonempty set with no accumulation point, and let $\abs{x - y}$ denote the [[Euclidean distance|0NPPGHQNXQ]].
The *Voronoi cell* of a point $p \in S$ is
$$V(p) = \set{x \in \R^n : \abs{x - p} \le \abs{x - q} \text{ for all } q \in S}.$$
If $\Lambda$ is a [[lattice|WN9V7WSJKF]] in $\R^n$, the *Voronoi cell of* $\Lambda$ is the cell $V(0)$ of the origin in $S = \Lambda$.

## Remarks

Each condition $\abs{x - p} \le \abs{x - q}$ defines a closed half-space, so $V(p)$ is a closed convex set.
Example: for $\Lambda = \Z^2$, the cell is $V(0) = [-\tfrac12, \tfrac12]^2$.
Indeed, $\abs{x} \le \abs{x - q}$ for $q = (\pm 1, 0)$ and $q = (0, \pm 1)$ gives $\abs{x_1} \le \tfrac12$ and $\abs{x_2} \le \tfrac12$, and these four conditions imply the others.
Non-example: the closed square $[0, 1]^2$ is not the Voronoi cell of $0$ in $\Z^2$, because its point $(1, 1)$ is at distance $0$ from $q = (1, 1)$ and at distance $\sqrt 2$ from $0$.
For a lattice $\Lambda$, the cell $V(0)$ is a convex polytope, symmetric about $0$, its translates $V(0) + v$ with $v \in \Lambda$ cover $\R^n$ with disjoint interiors, and its volume equals $\det \Lambda$.
The cells of all points of $S$ form the Voronoi diagram of $S$.