---
tag: V1R1R88GV6
kind: concept
name: Voronoi cell
msc: [52C07, 11H06, 52C22]
sources:
  - url: https://en.wikipedia.org/wiki/Voronoi_diagram
---

## Summary

Let $S$ be a discrete set of points in $\R^n$.
The Voronoi cell of $p \in S$ is the set of points that are no farther from $p$ than from any other point of $S$.
The Voronoi cells of the points of $S$ cover space and meet only along their boundaries.
For a [[lattice|WN9V7WSJKF]], all cells are translates of the cell of the origin.
This cell is a centrally symmetric convex polytope whose volume is the covolume of the lattice.
Voronoi cells of lattices are central in lattice packing and covering, in quantization and in decoding.

## Explanations

### L1 human

Imagine post offices at the points of $S$, and let everyone go to the nearest post office.
The Voronoi cell of a post office is the region of people who go to it.
For the integer grid $\Z^2$, the cell of the origin is the square of side $1$ centred at the origin.
For the hexagonal grid of a honeycomb, each cell is a regular hexagon.