K-Means Distance Computation

A Capital Group analytics workflow represents each observation and k-means centroid as a point in the same feature space. Implement compute_distances(points, centroids) to return the squared Euclidean distance from every point to every centroid.

For a point p and centroid c with d dimensions, compute:

distance(p, c) = sum((p[j] - c[j]) ** 2 for j in range(d))

Do not take the square root. K-means uses squared distances for cluster assignment, and omitting the square root is both sufficient and more efficient.

Formal Specification

• points is a non-empty list of n points.
• centroids is a non-empty list of k centroids.
• Each point and centroid is a list of d integers or floating-point values.
• Return an n x k list of lists, where result [i][j] is the squared distance from points[i] to centroids[j].
• Preserve the input ordering of both points and centroids.

Examples

Example 1

Input: points = [[1, 2], [4, 6]], centroids = [[0, 0], [5, 5]]

Output: [[5, 25], [52, 5]]

The first point is 5 units squared from [0, 0] and 25 units squared from [5, 5].

Example 2

Input: points = [[1, 1, 1]], centroids = [[1, 1, 1], [2, 3, 4]]

Output: [[0, 14]]

The point matches the first centroid exactly, while its squared distance to the second is 1 + 4 + 9 = 14.

Constraints

• 1 <= n, k <= 500
• 1 <= d <= 50
• All coordinates are between -10^6 and 10^6.
• Every point and centroid has exactly d coordinates.