next up previous contents
Next: What is the Delaunay Up: Voronoi Diagram and Delaunay Previous: What is cell complex?   Contents


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,

$\displaystyle 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.)


\includegraphics[height=40mm]{vtest_fig_vo}

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)$:

$\displaystyle \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.


\includegraphics[height=40mm]{vtest_fig_vo3d}


next up previous contents
Next: What is the Delaunay Up: Voronoi Diagram and Delaunay Previous: What is cell complex?   Contents
Komei Fukuda 2004-08-26