Best Position for a Service Centre

hard geometry gradient descent optimization

Problem

Given an array positions where positions[i] = [x, y] is the location of the i-th customer on a 2D map, choose a service-centre point [xc, yc] that minimizes the sum of Euclidean distances from the centre to every customer. Return that minimum total distance. Answers within 1e-5 of the true value are accepted.

Inputpositions = [[0,1],[1,0],[1,2],[2,1]]

Output4.00000

Placing the centre at (1, 1) puts every customer exactly 1 unit away, so the total is 4.

Inputpositions = [[1,1],[3,3]]

Output2.82843

Any point on the segment is optimal; the total is sqrt(2) + sqrt(2) = 2.82843.

positions (x:y, comma-separated)

def get_min_dist_sum(positions):
    def total(cx, cy):
        s = 0.0
        for px, py in positions:
            s += ((cx - px) ** 2 + (cy - py) ** 2) ** 0.5
        return s
    cx = sum(p[0] for p in positions) / len(positions)
    cy = sum(p[1] for p in positions) / len(positions)
    step, eps = 1.0, 1e-6
    dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    best = total(cx, cy)
    while step > eps:
        moved = False
        for ux, uy in dirs:
            nx, ny = cx + ux * step, cy + uy * step
            cand = total(nx, ny)
            if cand < best:
                cx, cy, best = nx, ny, cand
                moved = True
                break
        if not moved:
            step /= 2
    return best

function getMinDistSum(positions) {
  const total = (cx, cy) => {
    let s = 0;
    for (const [px, py] of positions)
      s += Math.hypot(cx - px, cy - py);
    return s;
  };
  let cx = positions.reduce((a, p) => a + p[0], 0) / positions.length;
  let cy = positions.reduce((a, p) => a + p[1], 0) / positions.length;
  let step = 1, best = total(cx, cy);
  const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  while (step > 1e-6) {
    let moved = false;
    for (const [ux, uy] of dirs) {
      const nx = cx + ux * step, ny = cy + uy * step;
      const cand = total(nx, ny);
      if (cand < best) { cx = nx; cy = ny; best = cand; moved = true; break; }
    }
    if (!moved) step /= 2;
  }
  return best;
}

double getMinDistSum(int[][] positions) {
    double cx = 0, cy = 0;
    for (int[] p : positions) { cx += p[0]; cy += p[1]; }
    cx /= positions.length; cy /= positions.length;
    double step = 1, best = total(positions, cx, cy);
    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    while (step > 1e-6) {
        boolean moved = false;
        for (int[] d : dirs) {
            double nx = cx + d[0] * step, ny = cy + d[1] * step;
            double cand = total(positions, nx, ny);
            if (cand < best) { cx = nx; cy = ny; best = cand; moved = true; break; }
        }
        if (!moved) step /= 2;
    }
    return best;
}
double total(int[][] pos, double cx, double cy) {
    double s = 0;
    for (int[] p : pos) s += Math.hypot(cx - p[0], cy - p[1]);
    return s;
}

double total(vector<vector<int>>& pos, double cx, double cy) {
    double s = 0;
    for (auto& p : pos) s += hypot(cx - p[0], cy - p[1]);
    return s;
}
double getMinDistSum(vector<vector<int>>& positions) {
    double cx = 0, cy = 0;
    for (auto& p : positions) { cx += p[0]; cy += p[1]; }
    cx /= positions.size(); cy /= positions.size();
    double step = 1, best = total(positions, cx, cy);
    int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    while (step > 1e-6) {
        bool moved = false;
        for (auto& d : dirs) {
            double nx = cx + d[0] * step, ny = cy + d[1] * step;
            double cand = total(positions, nx, ny);
            if (cand < best) { cx = nx; cy = ny; best = cand; moved = true; break; }
        }
        if (!moved) step /= 2;
    }
    return best;
}

Explanation

The point that minimizes the sum of Euclidean distances to a set of points is the geometric median. Unlike the centroid (which minimizes squared distance), it has no closed-form formula, so we search for it numerically.

The objective total(cx, cy) = Σ √((cx − px)² + (cy − py)²) is convex — it has a single bowl-shaped minimum with no local traps. That means a simple downhill search will always reach the global best.

We use a shrinking-step hill-descent. Start at the centroid (a good guess), then repeatedly try moving the current point by step in each of the four axis directions. If any move lowers the total distance, take it; if none of them helps, we are near the optimum at this resolution, so we halve the step and look more finely.

Each halving roughly doubles our precision. Starting from step = 1 and stopping at 1e-6 takes only about 20 halvings, so the answer easily lands within the required 1e-5 tolerance.

For the four-customer example the search converges on (1, 1), where every customer is exactly 1 unit away and the total is 4. This greedy descent is the same idea behind gradient descent and ternary/golden-section search in 2D.

Time: O(n · log(1/ε)) Space: O(1)