Compute Centroid

The centroid of a set of 2D points is just the average of all their coordinates, and it is used in alignment problems to “recentre” point sets so that translation is factored out before estimating rotation and scaling.

---

1. Background Knowledge

• Centroid definition For 2D points $p_i = (x_i, y_i)$, $i = 1,\dots,n$, the centroid is

$$\bar{x} = \frac{1}{n}\sum_{i=1}^n x_i,\qquad \bar{y} = \frac{1}{n}\sum_{i=1}^n y_i.$$

Geometrically, this is the “center of mass” if each point has equal mass.

• Why centering matters in alignment Many alignment methods (e.g., Procrustes analysis, ICP) first translate each point set so its centroid is at the origin. After this centering, any remaining difference between point sets is explained by rotation and scaling, making their estimation simpler (often via SVD or eigen-decomposition).

• Least squares connection The centroid minimizes the sum of squared Euclidean distances from all points to a single point:

$$\min_{c} \sum_{i=1}^n \|p_i - c\|^2.$$

The minimizer $c$ is exactly $($\bar{x}$,$\bar{y}$)$. This least-squares optimality is why centroids naturally appear in algorithms that minimize squared errors.

---

2. Algorithm / General Approach

The general pattern to compute a centroid:

1. Accumulate sums of all x-coordinates and y-coordinates.
2. Count the number of points $n$.
3. Divide sums by $n$ to get the average in each dimension.

This extends directly to higher dimensions: average each coordinate independently.

---

3. Step-by-Step Strategy

Assume input is a list/array of points, where each point is (x, y):

1. Initialize accumulators

sum_x = 0.0
sum_y = 0.0
n = len(points)

2. Edge case: if n == 0, decide how your problem specification says to handle it (often not allowed, or return a default/raise an error).

3. Loop through points and accumulate

for (x, y) in points:
sum_x += x
sum_y += y

4. Compute averages

cx = sum_x / n
cy = sum_y / n
centroid = (cx, cy)

5. Return or use the centroid (e.g., to subtract it from all points for centering):

centered_points = [(x - cx, y - cy) for (x, y) in points]

---

4. Common Pitfalls

• Empty input Division by zero if there are no points. Handle n == 0 explicitly.

• Integer division (in some languages)

• In languages like Python 2, C, C++, Java (with int), sum_x / n might do integer division.

• Ensure you use floating-point: cast either the sum or n to float (double) before division.

• Overflow / precision

• For very large coordinates or huge numbers of points, sums can overflow or lose precision.

• For an easy-level problem this is usually not relevant, but in high-precision applications you might consider more stable summation (e.g., Kahan summation).

• Coordinate order Make sure you are consistent with (x, y) ordering and do not mix them.

---

5. Time & Space Complexity

• Time complexity:

• Single pass over all points: $O(n)$.

• Space complexity:

• Only a few scalar accumulators plus the centroid: $O(1)$ extra space (ignoring the input storage).