Editing Voronoi diagram (section)

==Formal definition==
Let <math display="inline"> X </math> be a [[metric space]] with distance function <math display="inline">d</math>. Let <math display="inline">K</math> be a set of indices and let <math display="inline">(P_k)_{k \in K}</math> be a [[tuple]] (indexed collection) of nonempty [[subsets]] (the sites) in the space <math display="inline"> X</math>. The Voronoi cell, or Voronoi region,  <math display="inline"> R_k</math>, associated with the site <math display="inline">P_k</math> is the set of all points in <math display="inline">X</math> whose distance to <math display="inline"> P_k</math> is not greater than their distance to the other sites <math display="inline">P_j</math>, where <math display="inline">j</math> is any index different from <math display="inline">k</math>. In other words, if <math display="inline"> d(x,\, A) = \inf\{d(x,\, a) \mid a \in A\}</math> denotes the distance between the point <math display="inline">x</math> and the subset <math display="inline">A</math>, then

<math display="block"> R_k = \{x \in X \mid d(x, P_k) \leq d(x, P_j)\; \text{for all}\; j \neq k\}</math>

The Voronoi diagram is simply the [[tuple]] of cells <math display="inline">(R_k)_{k \in K} </math>. 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 polytope]]s 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 <math display="inline">R_k</math> is associated with a generator point  <math display="inline">P_k</math>.
Let <math display="inline">X</math> be the set of all points in the Euclidean space. Let <math display="inline">P_1</math> be a point that generates its Voronoi region  <math display="inline">R_1</math>, <math display="inline">P_2</math> that generates  <math display="inline">R_2</math>, and <math display="inline">P_3</math> that generates  <math display="inline">R_3</math>, and so on. <!--Then,

:<math> R_1 = \{x \in X \mid d(x, P_1) \leq d(x, P_2) \;\and\; d(x, P_1) \leq d(x, P_3) \;\and\; \ldots\}</math>
:<math> R_2 = \{x \in X \mid d(x, P_2) \leq d(x, P_1) \;\and\; d(x, P_2) \leq d(x, P_3) \;\and\; \ldots\}</math>
:...
--> Then, as expressed by Tran ''et al'',<ref name="Tran09">{{cite book |first1=Q. T. |last1=Tran |first2=D. |last2=Tainar |first3=M. |last3=Safar |date=2009 |title=Transactions on Large-Scale Data- and Knowledge-Centered Systems |page=357 |publisher=Springer |isbn=9783642037214}}</ref> "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".