k-Means Clustering and Cluster Geometry Notes for GATE DA: Concepts, Formulas, Worked Examples & Practice

k-Means Clustering and Cluster Geometry notes for GATE DA: 22 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Topic Hero: Convexity & The Midpoint Rule

Convexity & The Midpoint Rule

The geometric shortcut that solves assignment problems in seconds.

What you'll master:

Why Voronoi cells are strictly convex regions.
The "Line Segment Test" for cluster membership.
Solving exam-style "necessarily part of cluster" questions.

Context: Unsupervised Learning > k-Means Clustering > Geometry

The Convexity Property

A set $S$ is convex if for any two points $a, b \in S$ , the entire line segment connecting them lies within $S$ .

x (t) = (1 - t) a + t b for t \in [0, 1] ⟹ x (t) \in S

Voronoi cells are always convex.

This is because they are formed by the intersection of half-spaces (defined by perpendicular bisectors), and the intersection of convex sets (half-spaces) is always convex. Geometrically, this means a $k$ -means cluster can never wrap around another cluster or have a "C" shape.

The Line Segment Test

The Golden Rule of k-Means Geometry:

If points $p_{1}$ and $p_{2}$ belong to the same cluster $C_{k}$ , then any point $q$ lying on the line segment connecting $p_{1}$ and $p_{2}$ necessarily belongs to $C_{k}$ .

How to use it:

Identify two points known to be in the target cluster.
Check if any option point $q$ can be written as a convex combination:
$q = α p_{1} + (1 - α) p_{2} where 0 \leq α \leq 1$
If yes, $q$ is in the cluster.

Note: The midpoint ( $α = 0.5$ ) is the most common test case.

Worked Example: The Midpoint Shortcut

Given: Points $a = [11]$ and $b = [- 1 1]$ are in Cluster 3.

Question: Which point is necessarily in Cluster 3?

1. Check Origin $o = [00]$ : The segment lies on $y = 1$ . Origin has $y = 0$ . Not on segment.

2. Check Point $m = [01]$ : $m = 0.5 [11] + 0.5 [- 1 1] = [01]$ Since $m$ is the midpoint, it must be in Cluster 3.

More notes in this unit

chapter

k-Means Clustering and Cluster Geometry Notes for GATE DA: Concepts, Formulas, Worked Examples & Practice

k-Means Clustering and Cluster Geometry notes for GATE DA: 22 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice question

Free preview ends here

Login to view the complete notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free