Optimum location of point to minimize total distance

The problem, simply

You get some points on a flat map and a straight line, written as a*x + b*y + c = 0. Choose one spot on the line. Measure the straight distance from every point to that spot and add them up. Find the spot that makes this total as small as possible, and give back the smallest total.

The spot must be on the line. The distances are ordinary straight-line distances, not the shortest distance to the line.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk along the line in tiny steps and measure the total at every step. Keep the smallest.

1. Describe a spot on the line by one number t. If b is not 0, use x = t and y = -(a*t + c) / b. If b is 0 the line is straight up and down, so use y = t and x = -c / a.
2. The best spot lies between the leftmost and rightmost "drop points" (where each point would land if it dropped straight onto the line). Call those ends lo and hi.
3. Try t = lo, lo + step, lo + 2*step, ... up to hi, and keep the smallest total.

class Solution {
    double a, b, c;
    double[][] pts;

    // the spot on the line for the number t
    double[] spot(double t) {
        return b != 0 ? new double[]{t, -(a * t + c) / b} : new double[]{-c / a, t};
    }

    double total(double t) {
        double[] s = spot(t);
        double sum = 0;
        for (double[] p : pts) sum += Math.hypot(p[0] - s[0], p[1] - s[1]);
        return sum;
    }

    // where point p lands if it drops straight onto the line, as a t value
    double foot(double[] p) {
        double k = (a * p[0] + b * p[1] + c) / (a * a + b * b);
        return b != 0 ? p[0] - a * k : p[1] - b * k;
    }

    public double minTotal(double[][] points, double a, double b, double c) {
        this.pts = points; this.a = a; this.b = b; this.c = c;
        double lo = Double.MAX_VALUE, hi = -Double.MAX_VALUE;
        for (double[] p : pts) { lo = Math.min(lo, foot(p)); hi = Math.max(hi, foot(p)); }
        double best = Double.MAX_VALUE, step = 1e-3;
        for (double t = lo; t <= hi + step; t += step) {
            best = Math.min(best, total(t));     // try every small step
        }
        return best;
    }
}

How long it takes: if the range is R long, there are R / step spots and each costs n distances, so O(n * R/step). It is only as exact as the step, and a tiny step makes it very slow. Extra room: O(1).

Way 2: the clever way

The total walk, as the stop slides along the line, is shaped like a bowl: it goes down, then up, with no bumps. (Each house's own walk is a bowl, and adding bowls gives a bowl.) On a bowl you can use three-way search, a ternary search.

1. Start with the same lo and hi as Way 1.
2. Pick m1 = lo + (hi - lo) / 3 and m2 = hi - (hi - lo) / 3.
3. If total(m1) < total(m2), the bottom is not to the right of m2, so hi = m2. Otherwise the bottom is not to the left of m1, so lo = m1.
4. Repeat about 100 times. Each round keeps two thirds of the range, so the range shrinks very fast.
5. The answer is total((lo + hi) / 2).

class Solution {
    double a, b, c;
    double[][] pts;

    double[] spot(double t) {
        return b != 0 ? new double[]{t, -(a * t + c) / b} : new double[]{-c / a, t};
    }

    double total(double t) {
        double[] s = spot(t);
        double sum = 0;
        for (double[] p : pts) sum += Math.hypot(p[0] - s[0], p[1] - s[1]);
        return sum;
    }

    double foot(double[] p) {
        double k = (a * p[0] + b * p[1] + c) / (a * a + b * b);
        return b != 0 ? p[0] - a * k : p[1] - b * k;
    }

    public double minTotal(double[][] points, double a, double b, double c) {
        this.pts = points; this.a = a; this.b = b; this.c = c;
        double lo = Double.MAX_VALUE, hi = -Double.MAX_VALUE;
        for (double[] p : pts) { lo = Math.min(lo, foot(p)); hi = Math.max(hi, foot(p)); }
        for (int round = 0; round < 100; round++) {
            double m1 = lo + (hi - lo) / 3;
            double m2 = hi - (hi - lo) / 3;
            if (total(m1) < total(m2)) hi = m2;   // bottom is left of m2
            else lo = m1;                         // bottom is right of m1
        }
        return total((lo + hi) / 2);
    }
}

How long it takes: each round costs 2n distance sums and shrinks the range to two thirds, so reaching a precision eps takes O(log(R/eps)) rounds, O(n log(R/eps)) in all. 100 rounds shrink any range by a factor of more than 10^17. Extra room: O(1).

Watch out for

• A line with b = 0 is straight up and down. Then y = -(a*x + c)/b divides by zero. Use y as the moving number instead.
• Stopping with while (hi - lo > 1e-9) can loop forever when the numbers are big, because doubles cannot get that close. A fixed count of rounds is safe.
• Ternary search only works on a bowl with no flat bumps in the middle. Here a flat part can only happen at the very bottom, so it is safe.
• Print with the rounding the judge asks for, for example two digits after the point.

What interviewers ask next

• What if the stop can be anywhere on the map, not on a line? That is the geometric median. There is no simple formula, but Weiszfeld's method (a repeated weighted average) or gradient descent finds it.
• What if the walk is counted in city blocks, |dx| + |dy|? Then x and y split apart and the best spot is the median of the x values and the median of the y values. On a line with integer points, the median wins too.
• Why not binary search? Binary search needs a yes/no answer that flips once. A bowl gives "going down" then "going up", so you can binary search on the slope: compare total(m) with total(m + tiny). That is about as fast.
• Golden section search picks the two test spots so one of them is reused next round, saving half the work per round.

Remember this

Grown-up words: the bowl shape is a convex (unimodal) function, three-way search is ternary search, the drop point is the foot of the perpendicular, and the best stop with no line at all is the geometric median.