What is Voronoi diagram in $R^d$?

See also 3.3.

Given a set $S$ of $n$ distinct points in $R^d$, Voronoi diagram is the partition of $R^d$ into $n$ polyhedral regions $vo(p)$ ($p \in S$). Each region $vo(p)$, called the Voronoi cell of $p$, is defined as the set of points in $R^d$ which are closer to $p$ than to any other points in $S$, or more precisely,

$$vo(p) = \{ x \in R^d \vert dist(x, p) \leq dist(x, q) \quad \forall q\in S - p \},$$

where $dist$ is the Euclidean distance function. (One can use different distance functions to define various variations of Voronoi diagrams, but we do not discuss them here.)

The set of all Voronoi cells and their faces forms a cell complex. The vertices of this complex are called the Voronoi vertices, and the extreme rays (i.e. unbounded edges) are the Voronoi rays. For each point $v\in R^d$, the nearest neighbor set $nb(S, v)$ of $v$ in $S$ is the set of points $p \in S-v$ which are closest to $v$ in Euclidean distance. Alternatively, one can define a point $v\in R^d$ to be a Voronoi vertex of $S$ if $nb(S, v)$ is maximal over all nearest neighbor sets.

In order to compute the Voronoi diagram, the following construction is very important. For each point $p$ in $S$, consider the hyperplane tangent to the paraboloid in $R^{d+1}$ at $p$: $x_{d+1} = x_1^2 + \cdots + x_d^2$. This hyperplane is represented by $h(p)$:

$$\sum_{j=1}^d p_j^2 - \sum_{j=1}^d 2 p_j x_j + x_{d+1} = 0.$$

By replacing the equality with inequality $\ge$ above for each point $p$, we obtain the system of $n$ inequalities, which we denote by $b - A x \ge 0$. The polyhedron $P$ in $R^{d+1}$ of all solutions $x$ to the system of inequalities is a lifting of the Voronoi diagram to one higher dimensional space. In other words, by projecting the polyhedron $P$ onto the original $R^d$ space, we obtain the Voronoi diagram in the sense that the projection of each facet of $P$ associated with $p \in S$ is exactly the voronoi cell $vo(p)$. The vertices and the extreme rays of $P$ project exactly to the Voronoi vertices and the rays, respectively.