Optimum location of a point to minimise total distance
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
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);}