Problem statement

https://leetcode.com/problems/best-position-for-a-service-centre/

Solution

The idea is to write down convex optimization problem, the main difficulty is with gradient descent step-size. I tried 1/sqrt(i) as well as 1/i but due to the big range of possibilities, it can converge too slow. So, the alternative is to use so-called Weiszfelds algorithm, where stepsize is equal to inverse sum of inverse distances.

Complexity

Time complexity of algorithm is O(n*Q), where Q is number of iterations we make. Also we need to be careful: if dists = 0, it means that we converged to one of the points, so we break as well if the step we take is too small, we break as well.

Code

class Solution:
    def getMinDistSum(self, P):
        def dist(A, B, C, D):
            return sqrt((A-C)**2 + (B-D)**2)
        
        x, y, ans = 0.5, 0.5, float("inf")
        for i in range(1, 500):
            dists = [dist(x, y, xi, yi) for xi, yi in P]
            if 0 in dists: break
            step = 1/sum(1/t for t in dists)
            grad_x, grad_y = 0, 0
            for (xi, yi), d in zip(P, dists):
                if d == 0: continue
                grad_x += (x-xi)/d
                grad_y += (y-yi)/d
            if step*step*(grad_x**2 + grad_y**2) < 1e-13: break 
            x, y = x - step*grad_x, y - step*grad_y
            
        return sum(dist(x, y, xi, yi) for xi, yi in P)