Voronoi cells #

Background #

Consider a metric space \((S,\rho)\) and a family of points \(\{s_i\} \subset S.\) The Voronoi cell of a point \(s_i\) are exactly those points in \(S\) which are closer to \(s_i\) than any other point in this family. The collection of the cells for each of the points in \(\{s_i\}\) form a partition of \(S\). What is perhaps clear is that this partition depends on the choice of metric \(\rho\).

Three metrics #

Recall three metrics on \(\mathbb{R}^2\):

• \(\rho_1(x,y) = |x_1 - y_1| + |x_2 - y_2|\),
• \(\rho_2(x,y) = \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2}\), and
• \(\rho_\infty(x,y) = \max \{ |x_1 - y_1| , |x_2 - y_2|\}. \)

If your first analysis course was sufficiently pictorial, you may have been asked to draw the spheres of radius 1 around the origin for all three. The internet is full of such drawings.

Homework exercise: Consider the points \((-1,0)\) and \((2,1)\) in \(\mathbb{R}^2\).

• Draw the Voronoi partition of \(\mathbb{R}^2\) for these two points using each of the three metrics above.
• If you feel you have mastered this skill, also draw the Voronoi partition of \(\mathbb{R}^2\) induced by the points \((-1,-1)\) and \((1,1)\) using the \(\rho_1\) metric. Be careful.