325. Center of Gravity

The single-facility continuous-space location problem: place one facility anywhere in the plane to minimize total weighted distance to customers.

The optimal location is the Weber point (also called the geometric median).

325.1. Two flavors

Weighted centroid (squared Euclidean distance — easy):

— closed-form. The weighted mean. Used as a quick first approximation in network design.

Weber point (Euclidean distance — harder):

No closed form. Must iterate. The function is convex; standard methods converge.

325.2. Weiszfeld’s algorithm

For the Weber point, Weiszfeld iteration:

— a weighted average where weights are inverse distances: closer points pull more strongly.

Initialize x⁽⁰⁾ at the centroid
Repeat:
    Compute weights w_i = d_i / ||x⁽ᵏ⁾ - p_i||
    x⁽ᵏ⁺¹⁾ ← (Σ w_i p_i) / Σ w_i
Until convergence

Converges linearly. Caveat: if any iterate lands exactly on a customer point, the formula breaks (denominator ). Mitigation: small perturbation or alternate update rule when this occurs.

325.3. Geometric insight

The Weber point is Pareto-optimal: no infinitesimal move benefits any single weighted customer without harming the total. The gradient is zero — that’s exactly the Weiszfeld fixed-point condition.

325.4. Why use instead?

Sometimes Manhattan distance is more appropriate (grid streets, axis-aligned travel). Then the optimum is the coordinate-wise median:

— much simpler to compute than the Euclidean Weber point.

325.5. Where it shows up

In practice, center of gravity gives a continuous-space starting point that’s then snapped to the nearest feasible candidate (highway access, zoning, real estate availability).

325.6. See also