A Voronoi boundary

Topic: K-means clustering · more questions on this topic
‹ K-means by hand Reading the gap statistic ›

For centres (0,0), (4,2) and (0,4), find the three pairwise boundaries and verify that they meet at the circumcentre. What is the circumradius?

Worked answer (click to show)

Equal squared distances cancel the quadratic terms in the observation. What remains is linear, so each pair of centres supplies a perpendicular bisector.

For (0,0) and (4,2):

2(4,2)^\top\mathbf{x}=\|(4,2)\|^2-0,

that is 8x_1+4x_2=20, or 2x_1+x_2=5. For (0,0) and (0,4): 8x_2=16, so x_2=2. For (4,2) and (0,4):

2(-4,2)^\top\mathbf{x}=16-20,

that is -8x_1+4x_2=-4, or 2x_1-x_2=1. The first two meet where x_2=2 and 2x_1=3, so at (1.5,\ 2). The third equation gives 2(1.5)-2=1, which holds. The circumradius is the distance to any centre:

\sqrt{1.5^2+2^2}=2.5.

The distances to (4,2) and (0,4) are \sqrt{2.5^2+0}=2.5 and \sqrt{1.5^2+2^2}=2.5.