We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Best Position for a Service Centre

Number: 1638

Difficulty: Hard

Paid? No

Companies: Citadel

Problem Description

A delivery company wants to build a new service center such that the sum of the Euclidean distances from the center to all customer locations is minimized. Given an array of positions [[x₁, y₁], [x₂, y₂], ..., [xn, yn]], return the minimum possible sum of distances when the service center is optimally placed.

Key Insights

  • This is a geometric median problem where the goal is to minimize the sum of Euclidean distances.
  • Unlike the 1D case, the optimal point in 2D (known as the geometric median) is not simply the average or median of the coordinates.
  • Weiszfeld's algorithm is an iterative procedure used to approximate the geometric median.
  • With at most 50 points, an iterative approach with a convergence threshold (e.g., 10⁻⁵) is efficient.
  • Special care is needed to avoid division by zero when the current guess exactly matches a customer’s position.

Space and Time Complexity

Time Complexity: O(n * iterations), where n is the number of points and iterations is the number of update steps needed for convergence.
Space Complexity: O(n) for storing the positions.

Solution

We use Weiszfeld's algorithm to approximate the geometric median. The process starts with an initial guess (typically the centroid), and iteratively updates the guess using a weighted average of the customer positions. The weight for each point is the inverse of its distance from the current guess. The iterations stop when the movement between iterations is less than the threshold (e.g., 10⁻⁵). Finally, the sum of Euclidean distances is computed with the converged point.

Code Solutions

# Python implementation of Weiszfeld's algorithm for the geometric median.

def getMinDistance(positions):
    # Calculate initial guess as the centroid of all points.
    x = sum(pos[0] for pos in positions) / len(positions)
    y = sum(pos[1] for pos in positions) / len(positions)
    
    threshold = 1e-5  # Convergence threshold
    
    while True:
        numerator_x = 0
        numerator_y = 0
        denominator = 0
        
        # Weighted update step for the guess.
        for pos in positions:
            dx = x - pos[0]
            dy = y - pos[1]
            distance = (dx*dx + dy*dy) ** 0.5
            if distance < threshold:
                continue  # Skip to avoid division by zero.
            weight = 1 / distance
            numerator_x += pos[0] * weight
            numerator_y += pos[1] * weight
            denominator  += weight
        
        new_x = numerator_x / denominator
        new_y = numerator_y / denominator
        
        # Stop if the change in position is minimal.
        if ((x - new_x)**2 + (y - new_y)**2) ** 0.5 < threshold:
            x, y = new_x, new_y
            break
        x, y = new_x, new_y

    # Compute the total sum of distances.
    min_sum = 0
    for pos in positions:
        dx = x - pos[0]
        dy = y - pos[1]
        min_sum += (dx*dx + dy*dy) ** 0.5
        
    return min_sum

# Example usage:
positions1 = [[0,1],[1,0],[1,2],[2,1]]
print(getMinDistance(positions1))  # Expected output: 4.00000

positions2 = [[1,1],[3,3]]
print(getMinDistance(positions2))  # Expected output: 2.82843
← Back to All Questions