Optimum Location

Let’s take a point on the given line which is at an infinite distance from the origin. So, the distances of this point from the given set of points will be large and the sum will be equal to infinite. As we move along the line towards the range of points, this sum starts decreasing gradually. 

Then as we move again towards infinity in the opposite direction, the distances start increasing and the sum also reaches infinity. So, this means the sum is minimum at a particular point, and it starts increasing when we move in either direction on the line. If we plot the distance curve’s sum, it looks like a U-shaped curve as stated in the below figure.

So, our idea is to select a search range and search for the optimum points in that range. However, we can’t use linear search as the distances are not necessarily integers. We can’t use binary search as well as the U-shaped curve is not monotonically increasing or decreasing. So, we have to use a ternary search to find the optimum point. 

So, we take two values low and high. Initially low contains a very small value and high contains a very large value. These two values denote the range of X-coordinates of the points on the lines. Then we take mid1 and mid2, where mid1 is located at 1/3rd of the search space, and mid2 is located at 2/3rd. Find the Y-coordinate of the point on the line whose X-coordinate is mid1 and mid2 and then find the sum of the distances of the given set of points from this point. We compare both the distances and update the search space accordingly. We keep on doing the above step until the difference between low and high is negligible.

Steps:

• Take two variables of double data type named as low and high and initialize them to -10^6 and 10^6 respectively.
• While (high - low > (10^(-6))) do:
  • Create two variables of double data type named mid1 and mid2.
  • Initialize mid1 as low + (high - low) / 3 and mid2 as high - (high - low) / 3.
  • We create another function to find the sum of distances of a point to all the points in the points array. Let’s name this function as findSumOfDistances(line, points, x).
  • Store the sum of distances in distance1 and distance2 respectively, i.e. distance1 = findSumOfDistances(line, points, mid1) and distance2 = findSumOfDistances(line, points, mid2).
  • If distance1 < distance2, then make high = mid2.
  • Else, make low = mid1.
• Finally, as we come out of the loop, take a variable of type double, let’s call it x, which is the X-Coordinate of the optimum point. Make x = (low + high) / 2.
• Then, finally return findSumOfDistances(line, points, x).
• Note that here the initial values of low and high are given just for the sake of simplicity. We can improve this search space further by drawing perpendicular lines from all the points in the points array to the given line.
• Then we can initialize the values of low and high according to the X-Coordinates of the intersection points of perpendicular lines with the given line.

double findSumOfDistances(line, points, x):

• Create a variable of the double data type to store the sum of distances and initialize it to 0, i.e. double sum = 0.
• Find the Y-Coordinate of the point on the given line using the equation, i.e. y = -1/b(a * x + c).
• Run a loop i = 0 to N and do:
  • sum = sum + sqrt ((x - points[i].x)^2 + (y - points[i].y)^2).
• Finally, return the sum.

O(N * log3(C)), where N is the number of points in the “points” array/list and C is a constant which can range from -10^6 to 10^6.

The ternary search takes O(log 3(C)) time and in each step, we are calculating the sum of distances from a point to all the N points in the “points” array/list. Hence, the time complexity is O(N * log3(C)).

O(1)

Constant space is used.