Optimum location of a point to minimise total distance

Hard

Problem

Given points and a line ax + by + c = 0, find the point on the line that minimises the sum of Euclidean distances to all the points. Return that minimum sum. The sum is unimodal along the line, so ternary search works.

Example 1

Input:  line x − y − 3 = 0, points [(-3,-2), (-1,0), (-1,2), (1,2), (3,4)]
Output: ≈ 20.77

Also asked as: Optimum location of point to minimize total distance

Test cases

Case 1

Input:    [[-3,-2],[-1,0],[-1,2],[1,2],[3,4]], [1,-1,-3]
Expected: 20.765235034641616

Case 2

Input:    [[0,0]], [1,-1,-3]
Expected: 2.1213203435596424

Case 3

Input:    [[0,3],[0,-3]], [0,1,0]
Expected: 6

Case 4

Input:    [[1,1]], [1,-1,0]
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Ternary search on the line (convex objective)

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

The sum of Euclidean distances from a point on a given line to fixed points is a convex function of the position along the line, so ternary-search the parameter.

function optimumLocation(points, line) { // line: [a, b, c] for ax + by + c = 0
const [a, b, c] = line;
const pointAt = (t) => {
// parametrise the line; here assume b !== 0: x = t, y = -(a*t + c)/b
return [t, -(a * t + c) / b];
};
const cost = (t) => {
const [x, y] = pointAt(t);
return points.reduce((s, [px, py]) => s + Math.hypot(px - x, py - y), 0);
};
let lo = -1e6, hi = 1e6;
for (let iter = 0; iter < 200; iter++) {
const m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3;
if (cost(m1) < cost(m2)) hi = m2; else lo = m1;
}
return cost(lo);
}