Voronoi diagram is a diagram for set $P$ of $N$ points from $\mathbb R^n$ space (generally to any set $X$). It is constructed by splitting $\mathbb R^n$ space into $N$ subspaces $A_i$, in such a way that arbitrary point $x\in\mathbb R^n$ belongs to $A_i$, only if point $p_i\in P$ is the nearest point to $x$ for given metric $d$. From the mathematical perspective one can define each subspace in the following way:

$A_i = \{ x\in \mathbb R^n : \forall_{i\neq j} d(x,p_i) \le d(x,p_j) \}, \$

where $d(x,y)$ is given metric. One can use an arbitrary metric. However, most common ones are Euclidean (standard) and Manhattan (sometimes referred to as taxicab) metrics. The first defined by function: $d(x,y) = \sqrt{\displaystyle\sum_{i=1}^{n}(x_i-y_i)^2}$ and the other one by: $d(x,y) = \displaystyle\sum_{i=1}^n |x_i-y_i|$. Voronoi diagrams are very useful. There can be found in many aspects of our lives: in natural sciences, engineering, geometry, computer games or even in medicine. The main goal of the post is to introduced to the reader some basics concepts and thought regarding the Voronoi diagram. I prepared some basics scripts in gnuplot and python to present to you some methods for solving this kind of problem. Let’s begin with the simple brute-force algorithm in python. From now on we will be focus only on $n=2$ case. Below a simple program is presented. Here we assume that we work in a square area: $(x,y)\in \mathbb R^2, 0 \le x,y \le$L. we generate 20 points and we sample points in a square with L/samples steps and for each we check, which point from data is the nearest.

After the procedure, one can visualize the results using gnuplot program. Our output has the following form: $x$, $y$, $i$, where $i$ is the index of subspace $A_i$.

where voronoi.py is the filename of the previous python script. Here you have an example and comparison of these two different metrics on the same random points:

As you can see the result with the Manhattan metric is similar to a polyline. Each area’s border is a polyline, in contrast to the Euclidean metric, where borders between neighbors’ areas are just straight lines. In many blogs, websites, people explain Voronoi diagrams by using some graphical programs. By generating cones, one can find the Voronoi diagram (for Euclidean metric) by simply searching for the intersection between them. However, I have never seen a solution to the problem, which was fully designed in gnuplot. Gnuplot is plotting and also a graphical program. Most of the community presents an example only using the cones, but similar understanding can be considered for other geometric objects, for example for pyramids to solve the problem in Manhattan metric.

The problem comes down to simply drawing the selected geometrical shapes. Then one should only map these objects into $xy$ plain. Here a gnuplot example is presented:

In the previous code snippet, there is another variable, which can be changed: distance radius r. Changing r value, creation of the intersection between objects can be seen. In the next animations, this phenomenon was presented.

In this post, the simplest solutions to these kinds of problems were presented. There are many more (much more sophisticated) algorithms. Probably the famous one: Fortune’s algorithm.

AW