In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. It can be classified also as a tessellation. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed there is a corresponding region, called a Voronoi cell, consisting of all points of the plane closer to that seed than to any other. The Voronoi diagram of a set of points is dual to that set's Delaunay triangulation.

The Voronoi diagram is named after mathematician Georgy Voronoy, and is also called a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation (after Peter Gustav Lejeune Dirichlet). Voronoi cells are also known as Thiessen polygons, after Alfred H. Thiessen.^[1][2][3] Voronoi diagrams have practical and theoretical applications in many fields, mainly in science and technology, but also in visual art.^[4][5]

The simplest case

In the simplest case, shown in the first picture, we are given a finite set of points ${\displaystyle \{p_{1},\dots p_{n}\}}$ in the Euclidean plane. In this case each site ${\displaystyle p_{k}}$ is one of these given points, and its corresponding Voronoi cell ${\displaystyle R_{k}}$ consists of every point in the Euclidean plane for which ${\displaystyle p_{k}}$ is the nearest site: the distance to ${\displaystyle p_{k}}$ is less than or equal to the minimum distance to any other site ${\displaystyle p_{j}}$. For one other site ${\displaystyle p_{j}}$, the points that are closer to ${\displaystyle p_{k}}$ than to ${\displaystyle p_{j}}$, or equally distant, form a closed half-space, whose boundary is the perpendicular bisector of line segment ${\displaystyle p_{j}p_{k}}$. Cell ${\displaystyle R_{k}}$ is the intersection of all of these ${\displaystyle n-1}$ half-spaces, and hence it is a convex polygon.^[6] When two cells in the Voronoi diagram share a boundary, it is a line segment, ray, or line, consisting of all the points in the plane that are equidistant to their two nearest sites. The vertices of the diagram, where three or more of these boundaries meet, are the points that have three or more equally distant nearest sites.

Formal definition

Let ${\textstyle X}$ be a metric space with distance function ${\textstyle d}$. Let ${\textstyle K}$ be a set of indices and let ${\textstyle (P_{k})_{k\in K}}$ be a tuple (indexed collection) of nonempty subsets (the sites) in the space ${\textstyle X}$. The Voronoi cell, or Voronoi region, ${\textstyle R_{k}}$, associated with the site ${\textstyle P_{k}}$ is the set of all points in ${\textstyle X}$ whose distance to ${\textstyle P_{k}}$ is not greater than their distance to the other sites ${\textstyle P_{j}}$, where ${\textstyle j}$ is any index different from ${\textstyle k}$. In other words, if ${\textstyle d(x,\,A)=\inf\{d(x,\,a)\mid a\in A\}}$ denotes the distance between the point ${\textstyle x}$ and the subset ${\textstyle A}$, then

$${\displaystyle R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{for all}}\;j\neq k\}}$$

The Voronoi diagram is simply the tuple of cells ${\textstyle (R_{k})_{k\in K}}$. In principle, some of the sites can intersect and even coincide (an application is described below for sites representing shops), but usually they are assumed to be disjoint. In addition, infinitely many sites are allowed in the definition (this setting has applications in geometry of numbers and crystallography), but again, in many cases only finitely many sites are considered.

In the particular case where the space is a finite-dimensional Euclidean space, each site is a point, there are finitely many points and all of them are different, then the Voronoi cells are convex polytopes and they can be represented in a combinatorial way using their vertices, sides, two-dimensional faces, etc. Sometimes the induced combinatorial structure is referred to as the Voronoi diagram. In general however, the Voronoi cells may not be convex or even connected.

In the usual Euclidean space, we can rewrite the formal definition in usual terms. Each Voronoi polygon ${\textstyle R_{k}}$ is associated with a generator point ${\textstyle P_{k}}$. Let ${\textstyle X}$ be the set of all points in the Euclidean space. Let ${\textstyle P_{1}}$ be a point that generates its Voronoi region ${\textstyle R_{1}}$, ${\textstyle P_{2}}$ that generates ${\textstyle R_{2}}$, and ${\textstyle P_{3}}$ that generates ${\textstyle R_{3}}$, and so on. Then, as expressed by Tran et al,^[7] "all locations in the Voronoi polygon are closer to the generator point of that polygon than any other generator point in the Voronoi diagram in Euclidean plane".

Illustration

As a simple illustration, consider a group of shops in a city. Suppose we want to estimate the number of customers of a given shop. With all else being equal (price, products, quality of service, etc.), it is reasonable to assume that customers choose their preferred shop simply by distance considerations: they will go to the shop located nearest to them. In this case the Voronoi cell ${\displaystyle R_{k}}$ of a given shop ${\displaystyle P_{k}}$ can be used for giving a rough estimate on the number of potential customers going to this shop (which is modeled by a point in our city).

For most cities, the distance between points can be measured using the familiar Euclidean distance:

${\displaystyle {\mathrm{\ell <!--\; \ell \; -->}}_{}}$Zdroj:https://en.wikipedia.org?pojem=Thiessen_polygon
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

---