Optimum location of point to minimize total distance

Problem Statement

Given a set of points on a line and a line equation (y = mx + c), find the point on the line such that the sum of distances from all given points to this point is minimized.

Constraints:

• Points are given as (x, y) coordinates
• The line is given by equation y = mx + c
• Find the optimal x-coordinate on the line

Example:

• Input: points = [(0, 1), (2, 3), (4, 5)], line: y = x + 1
• Output: The x-coordinate that minimizes total distance to all points

Note: This problem uses Ternary Search because the distance function is unimodal (first decreases, then increases).

Understanding the Problem

For a point (xi, yi) and a line y = mx + c, the perpendicular distance from the point to the line is:

Since sqrt(m² + 1) is constant for a given line, we minimize:

The function f(x) is convex (V-shaped or bowl-shaped), making it suitable for ternary search.

Approach 1: Brute Force (Linear Search)

Intuition

Check all possible x-coordinates within a range and find the one that minimizes total distance.

Algorithm

1. Define a search range [low, high]
2. Try each x-coordinate with small increments
3. Calculate total distance for each x
4. Return x with minimum total distance

public class Solution {
    static class Point {
        double x, y;
        Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }
    
    private double distanceSum(Point[] points, double m, double c, double x) {
        double sum = 0;
        double y = m * x + c;
        
        for (Point p : points) {
            sum += Math.sqrt(Math.pow(p.x - x, 2) + Math.pow(p.y - y, 2));
        }
        
        return sum;
    }
    
    public double findOptimalPoint(Point[] points, double m, double c) {
        double low = -1e6, high = 1e6;
        double step = 0.001;
        double minDist = Double.MAX_VALUE;
        double result = low;
        
        for (double x = low; x <= high; x += step) {
            double dist = distanceSum(points, m, c, x);
            if (dist < minDist) {
                minDist = dist;
                result = x;
            }
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n × range/step) - Checking many points
• Space Complexity: O(1) - Only using variables

Approach 2: Ternary Search (Optimal)

Intuition

Since the total distance function is unimodal (convex), we can use ternary search to find the minimum. Ternary search divides the search space into three parts and eliminates one-third of the space in each iteration.

Algorithm

1. Define search range [low, high]
2. While high - low > epsilon:
   • Calculate mid1 = low + (high - low) / 3
   • Calculate mid2 = high - (high - low) / 3
   • If f(mid1) < f(mid2), search [low, mid2]
   • Else search [mid1, high]
3. Return (low + high) / 2

public class Solution {
    static class Point {
        double x, y;
        Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }
    
    private double distanceSum(Point[] points, double m, double c, double x) {
        double sum = 0;
        double y = m * x + c;
        
        for (Point p : points) {
            sum += Math.sqrt(Math.pow(p.x - x, 2) + Math.pow(p.y - y, 2));
        }
        
        return sum;
    }
    
    public double ternarySearch(Point[] points, double m, double c) {
        double low = -1e6, high = 1e6;
        double epsilon = 1e-9;
        
        while (high - low > epsilon) {
            double mid1 = low + (high - low) / 3;
            double mid2 = high - (high - low) / 3;
            
            double dist1 = distanceSum(points, m, c, mid1);
            double dist2 = distanceSum(points, m, c, mid2);
            
            if (dist1 < dist2) {
                high = mid2;
            } else {
                low = mid1;
            }
        }
        
        return (low + high) / 2;
    }
}

Visual Understanding

Dry Run Example

Complexity Analysis

• Time Complexity: O(n × log(range/epsilon)) - Ternary search with n points per evaluation
• Space Complexity: O(1) - Only using variables

Approach 3: Iteration-Limited Ternary Search

For competitive programming, often a fixed number of iterations is used instead of epsilon comparison.

Golden Section Search (Alternative)

An alternative to ternary search with slightly better convergence.

Key Takeaways

1. Ternary Search Application: Used when function is unimodal (has single minimum or maximum)
2. Convex Functions: Sum of distances is convex, making ternary search applicable
3. Convergence: Each iteration reduces search space by 1/3
4. Iterations vs Epsilon: Fixed iterations (100) often preferred for reliability
5. Golden Section: Slightly more efficient alternative to ternary search
6. Common Applications:
   • Finding optimal location problems
   • Minimizing/maximizing convex functions
   • Binary search on answer with convex validation function