Best Position for a Service Centre: The Geometric Median

You are given a list of customer positions on a 2D plane. Find the position [x, y] that minimizes the sum of Euclidean distances to all customers. Return the minimum total distance.

This is LeetCode 1515: Best Position for a Service Centre, and it asks you to compute the geometric median of a set of points. Unlike the arithmetic mean (centroid), the geometric median minimizes total distance rather than total squared distance. There is no closed-form formula, so you need an iterative numerical method.

Why the centroid is not the answer

Your first instinct might be to just average all the x-coordinates and all the y-coordinates. That gives you the centroid, which minimizes the sum of squared distances. But the problem asks for the sum of Euclidean distances (not squared). These are different objectives, and they produce different optimal points.

The centroid is a good starting point, though. It is close to the geometric median and easy to compute, making it an ideal initial guess for iterative refinement.

The approach: Weiszfeld's algorithm

Weiszfeld's algorithm is a classic iterative method for computing the geometric median. It works by repeatedly computing a weighted average of the input points, where each weight is the reciprocal of the distance from the current estimate to that point.

Given the current estimate (cx, cy), the update rule is:

• For each customer i at position (xi, yi), compute the weight w_i = 1 / dist((cx, cy), (xi, yi))
• The new estimate is (sum(w_i * xi) / sum(w_i), sum(w_i * yi) / sum(w_i))

Points that are closer to the current estimate get higher weights, which makes sense: the objective function (sum of distances) is more sensitive to nearby points than distant ones. Each iteration is guaranteed to decrease the total distance, and the algorithm converges to the optimal solution.

The solution

def getMinDistSum(positions):
    cx = sum(p[0] for p in positions) / len(positions)
    cy = sum(p[1] for p in positions) / len(positions)

    for _ in range(1000):
        wx, wy, wt = 0.0, 0.0, 0.0
        for px, py in positions:
            d = ((cx - px) ** 2 + (cy - py) ** 2) ** 0.5
            if d < 1e-8:
                continue
            w = 1.0 / d
            wx += w * px
            wy += w * py
            wt += w
        if wt == 0:
            break
        nx, ny = wx / wt, wy / wt
        if abs(nx - cx) + abs(ny - cy) < 1e-7:
            break
        cx, cy = nx, ny

    return sum(((cx - px) ** 2 + (cy - py) ** 2) ** 0.5 for px, py in positions)

The code starts at the centroid, then runs Weiszfeld iterations until the position change is negligibly small. The 1e-8 guard in the denominator prevents division by zero when the current estimate coincides with a customer position.

Step-by-step walkthrough

Let's trace through the example with positions = [[0,1],[1,0],[1,2],[2,1],[3,3]].

Notice how each iteration reduces the total distance. The first few steps make the biggest corrections, and the updates shrink rapidly. This is typical of Weiszfeld's algorithm, which has linear convergence in most cases.

Alternative: gradient descent with shrinking step size

Another valid approach is to use gradient descent. The gradient of the total distance function with respect to (cx, cy) is the sum of unit vectors from each customer to the centre. You move in the negative gradient direction with a step size that shrinks over time.

def getMinDistSum(positions):
    cx = sum(p[0] for p in positions) / len(positions)
    cy = sum(p[1] for p in positions) / len(positions)
    step = 1.0

    def total_dist(x, y):
        return sum(((x - px) ** 2 + (y - py) ** 2) ** 0.5 for px, py in positions)

    cur = total_dist(cx, cy)
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        while step > 1e-7:
            nx, ny = cx + step * dx, cy + step * dy
            nd = total_dist(nx, ny)
            if nd < cur:
                cur = nd
                cx, cy = nx, ny
            else:
                step /= 2
    return cur

This simulated annealing variant tries all four directions and halves the step size when no improvement is found. It is simpler to reason about but slower to converge than Weiszfeld.

Complexity analysis

Where n is the number of positions and k is the number of iterations until convergence. In practice, k is small (typically under 100 for the problem constraints). Both approaches use O(1) extra space since they only maintain the current estimate.

The building blocks

This problem is built on iterative numerical optimization. You start with an initial guess and refine it step by step until convergence. This same template appears whenever there is no closed-form solution and you need to minimize a continuous objective function.

The key insight is recognizing that the sum of Euclidean distances does not have a neat algebraic solution like the sum of squared distances. Once you know that, the path forward is clear: pick an iterative method (Weiszfeld or gradient descent), start from a reasonable initial guess (the centroid), and iterate until the improvement is negligible.

The weighted average update in Weiszfeld's algorithm is worth remembering as a standalone technique. It comes up in other geometric optimization problems and in machine learning (e.g., iteratively reweighted least squares).

Edge cases

• All customers at the same point: the optimal centre is that point. Total distance is 0. The centroid equals the geometric median.
• Two customers: the geometric median lies on the line segment between them. Any point on the segment minimizes total distance (they are all equal). The centroid works.
• Customer at the current estimate: the weight would be 1/0. Skip that point in the Weiszfeld update (it already contributes zero distance). The d < 1e-8 guard handles this.
• Collinear points: the geometric median still lies among the points, not necessarily at the centroid. Weiszfeld handles this correctly.
• Single customer: return distance 0. The optimal centre is the customer's location.

From understanding to recall

The hardest part of this problem is not the algorithm itself. Weiszfeld's update rule is just a weighted average. The hard part is remembering to use it when you see a geometric median problem in an interview. If you have never drilled this pattern, you will likely waste time trying to derive the gradient from scratch or attempting a binary search approach that does not work in 2D.

Spaced repetition locks in the connection between "minimize sum of Euclidean distances" and "Weiszfeld's algorithm." After a few reps, the moment you read a problem statement like this, the approach clicks instantly. That recall speed is the difference between solving a hard problem in 15 minutes and struggling for 45.

Related posts

• K Closest Points to Origin - Another 2D geometry problem using Euclidean distance, though it uses sorting/heap selection rather than numerical optimization
• Minimum Cost to Hire K Workers - A different optimization problem where you minimize a continuous cost function using a greedy heap approach
• Best Sightseeing Pair - An optimization problem that decomposes a sum into tractable subproblems, showing another style of "find the best" thinking