GATE 2024 DA Q.19: solution and answer

Official answer: DSource: Official answer key, GATE 2024 DA (IISc Bengaluru)

1. In $k$-means with Euclidean distance, a point belongs to cluster 3 when its nearest centroid is ${\mu }_3$. So cluster 3 is the set $\{x:\Vert x-{\mu }_3\Vert \le \Vert x-{\mu }_j\Vert \text{ for }j=1,2\}$.

2. Expand $\Vert x-{\mu }_3{\Vert }^2\le \Vert x-{\mu }_j{\Vert }^2$. The $\Vert x{\Vert }^2$ terms cancel, leaving $2({\mu }_j-{\mu }_3{)}^{\top }x\le \Vert {\mu }_j{\Vert }^2-\Vert {\mu }_3{\Vert }^2$. This is a half-plane, so cluster 3's region is an intersection of half-planes (a Voronoi cell) and is convex.

3. Both $\left[\begin{array}{c}1\\ 1\end{array}\right]$ and $\left[\begin{array}{c}-1\\ 1\end{array}\right]$ lie in this convex region, so every point of the segment joining them also lies in it. The segment is $\{(t,1):-1\le t\le 1\}$.

4. The midpoint is $\left(\frac{1+(-1)}{2},\frac{1+1}{2}\right)=(0,1)$, which is option (D). So (D) is necessarily in cluster 3, apart from the degenerate case of an exact tie between centroids.

5. The other options are not guaranteed. Take ${\mu }_3=(0,1)$ and put another centroid exactly at the option point $p$. Then $\Vert (\pm 1,1)-{\mu }_3\Vert =1$, while the distance from $(\pm 1,1)$ to $p$ is at least $\sqrt{2}$ for $p=(0,0)$ and $p=(0,2)$, and at least $\sqrt{2}$ for $p=(2,0)$ (distances $\sqrt{2}$ and $\sqrt{10}$). So both given points stay in cluster 3. But $p$ is at distance $0$ from its own centroid, so $p$ is in a different cluster. Hence (A), (B) and (C) are not necessarily in cluster 3.