Editing Voronoi diagram (section)

==Simplest case==
In the simplest case, shown in the first picture, we are given a finite set of points <math>\{p_1,\dots p_n\}</math> in the [[Euclidean plane]]. In this case, each point <math>p_k</math> has a corresponding cell <math>R_k</math> consisting of the points in the Euclidean plane for which <math>p_k</math> is the nearest site: the distance to <math>p_k</math> is less than or equal to the minimum distance to any other site <math>p_j</math>. For one other site <math>p_j</math>, the points that are closer to <math>p_k</math> than to <math>p_j</math>, or equally distant, form a [[Half-space (geometry)|closed half-space]], whose boundary is the [[perpendicular bisector]] of line segment <math>p_jp_k</math>. Cell <math>R_k</math> is the intersection of all of these <math>n-1</math> half-spaces, and hence it is a [[convex polygon]].<ref>{{cite book |last1=Boyd |first1=Stephen |last2=Vandenberghe |first2=Lieven |title=Convex Optimization |date=2004 |publisher=Cambridge University Press |location=Exercise 2.9 |page=60}}</ref> When two cells in the Voronoi diagram share a boundary, it is a [[line segment]], [[ray (geometry)|ray]], or line, consisting of all the points in the plane that are equidistant to their two nearest sites. The [[vertex (geometry)|vertices]] of the diagram, where three or more of these boundaries meet, are the points that have three or more equally distant nearest sites.