Voronoi Tessellation

 We now consider models for planar point patterns which consist of two (or even more) different types of points, say $x_1,\ldots,x_{n_1}$ and $y_1,\ldots,y_{n_2}$. These models can be used to analyze the spatial organization of hierarchical communication networks. Suppose for example that we are considering the locations of subscribers and stations respectively in a certain geographical region. The cells handled by stations in communication networks are often far from the regular hexagonal shape which is usually taken as a reference model; see Lee (1993, 1995). An alternative approach which allows one to take these fluctuations into account is based on the idea of considering not only the observed configuration $\{x_1,\ldots,x_{n_1}\}$ of subscribers but also the locations $\{y_1,\ldots,y_{n_2}\}$ of stations as a realization of a planar point process in a certain geographical region; see Baccelli et al. (1996), Baccelli and Zuyev (1997, 1998), Foss and Zuyev (1996), Zuyev et al. (1997). This kind of stochastic modeling is quite natural in macro-economic studies of cellular communication systems.

Assume that subscribers are served by the nearest station. This means that each station serves subscribers located in a certain region. In other words, the plane is divided into convex polygonal cells, each of which is served by a unique station (see Figure 9).

 

Figure 9:  Tessellation

Such a division of the plane is called a tessellation or mosaic if the constituent polygons are bounded and pairwise disjoint, the union of their closures fills the plane, and the family of polygons is locally finite, i.e., finite on any bounded region.

In connection with the above mentioned division of the plane by a family of spatially distributed stations, we are particularly interested in the following kind of tessellation which is induced by a locally finite sequence $\{y_1, y_2, \ldots \}$ of points in $\RL^2$. Let c_n denote the set of all $y \in \RL^2$ for which y_n is the nearest point from $\{y_1, y_2, \ldots \}$, that is  

$$c_n = \{ y \in \RL^2 \, : \, \vert y - y_n\vert < \vert y-y_m\vert, \; m\neq n\}.$$ (1)

The $c_1, c_2, \ldots$ are all open convex polygons but some of them can be unbounded. However, if the sequence $\{y_1, y_2, \ldots \}$ is chosen in such a way that this deficiency does not arise, then $\{c_1,c_2,\ldots\}$ constitutes a so-called Voronoi tessellation with respect to $y_1,y_2,\ldots$The convex polygon c_n is called the Voronoi cell with nucleus y_n; see e.g. Aurenhammer (1991), Boots (1987), Okabe et al. (1992). Note, however, that some authors speak of a Dirichlet or Thiessen tessellation, instead of a Voronoi tessellation.

Assume that $\{c_1,c_2,\ldots\}$ is a Voronoi tessellation such that every node $\star$ is touched by exactly three cells, as in Figure 10(a). Then a further tessellation can be considered, the so-called Delaunay tessellation which is constructed by linking all those pairs from $\{y_1, y_2, \ldots \}$ which belong to neighboring cells of the Voronoi tessellation. These links, i.e., the edges of the Delaunay tessellation, can model cables connecting the neighboring stations located at the points $y_1,y_2,\ldots$In Figure 10(b) a realization of a Delaunay tessellation is given, where the solid lines are the links which connect the neighboring stations.

 

Figure 10:   Construction of a Delaunay tesselation