Center of Gravity

328. 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).

328.1. Two flavors

Weighted centroid (squared Euclidean distance — easy):

min \sum_{𝑖} 𝑑_{𝑖} ‖ 𝑥 - 𝑝_{𝑖} ‖^{2} \Rightarrow 𝑥^{*} = \frac{\sum_{𝑖} 𝑑_{𝑖} 𝑝_{𝑖}}{\sum_{𝑖} 𝑑_{𝑖}}

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

Weber point (Euclidean distance — harder):

min \sum_{𝑖} 𝑑_{𝑖} ‖ 𝑥 - 𝑝_{𝑖} ‖

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

328.2. Weiszfeld’s algorithm

For the Weber point, Weiszfeld iteration:

𝑥^{(𝑘 + 1)} = \frac{\sum_{𝑖} 𝑑_{𝑖} \frac{𝑝_{𝑖}}{‖} 𝑥^{(𝑘)} - 𝑝_{𝑖} ‖}{\sum_{𝑖} \frac{𝑑_{𝑖}}{‖} 𝑥^{(𝑘)} - 𝑝_{𝑖} ‖}

— 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 $= 0$ ). Mitigation: small perturbation or alternate update rule when this occurs.

Iterating from the centroid (dashed ring), the trail converges to the Weber point (diamond); spokes connect the optimum to each customer (sized by weight):

328.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.

328.4. Why use $𝐿^{1}$ instead?

Sometimes Manhattan distance $\sum_{𝑖} 𝑑_{𝑖} (| 𝑥_{1} - 𝑝_{𝑖, 1} | + | 𝑥_{2} - 𝑝_{𝑖, 2} |)$ is more appropriate (grid streets, axis-aligned travel). Then the optimum is the coordinate-wise median:

𝑥_{1}^{*} = weighted median of 𝑝_{𝑖, 1}, 𝑥_{2}^{*} = weighted median of 𝑝_{𝑖, 2}

— much simpler to compute than the Euclidean Weber point.

328.5. Where it shows up

Distribution-center placement — first approximation before discrete refinement
Field service hubs
Hospital emergency response
Server placement in computer networks

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).

328.6. See also

$𝑝$ -median — discrete, multi-facility
Facility Location overview
Daganzo Continuous Approximation — strategic-level