Find point using distance from any other point with minimum steps

Question

I need to find a point in 3d space with a function that returns the distance between that point and any other point of my choosing. all the coordinates can vary from 0 to 100 and only can be integers. Of course, I could use brute force, but the complexity will be n^3, and that’s way too far from minimum steps

I was trying to reach the solution using binary search, because we can imagine, that I have an array from 0 to 100, where each point represents some axis, x-axis for example. And by moving either to the left or to the right I will be moving closer to the point, but my solution does not work correctly

This is the code I could come up with. At some points it works, but not all

const findClosestX = (low, high, destinationPoint) => {
  const middle = Math.floor((low + high) / 2);

  const starting_distance = new Point(middle, 0, 0).getDistance(destinationPoint);

  // Point class is simple object with x,y,z coordinates and function
  // for getting distance between points
  const distance_1 = new Point(low, 0, 0).getDistance(destinationPoint);
  const distance_2 = new Point(high, 0, 0).getDistance(destinationPoint);

  const minPoint = Math.min(starting_distance, distance_1, distance_2);

  if (minPoint === starting_distance) {
    return middle;
  } else if (minPoint === distance_1) return findClosestX(low, middle - 1, destinationPoint);
  else if (minPoint === distance_2) return findClosestX(middle + 1, high, destinationPoint);
};

Answer 1

For the one-dimensional case there's the bisection method which is the continuous version of the well known binary search algorithm.

It is used to find the solution of an equation, that is the zero of a function f(x) = 0, in an interval [a, b], where the function is monotonous (increasing or decreasing), and f(a) > 0 and f(b) < 0 (or f(a) < 0, f(b) > 0), which guarantees that there is exactly one solution in the interval [a, b].

It consists in a loop that maintains three points: left, right and middle.

• Initially, they are the a, b and (a+b)/2.

• At each step it updates the three points by either:

  1. choosing the middle point to be the next left point (chooses the right half, the new interval is [middle, right])
  2. choosing the middle point to be the right point (chooses the left half, the new interval is [left, middle]).

  The next middle will be computed as the middle of the new interval.

• the choice between the variants above is made in such a way that the sign of the f(left) is the same as the sign of f(a) and the sign of the f(right) is the same as f(b). This guarantees that the solution is always inside the interval [left, right] and since the interval is always shrinking (it's half the length of the interval in the previous step) it's guaranteed to get ever close to the true solution.

• the iteration is stopped when the current middle point is close enough to the solution |f(middle)| < eps

---

The first step in adjusting this algorithm to the problem here is the most sensitive: making the algorithm work for an optimization problem. I'll restrict the analysis to a minimization problem, as it is the case here.

The change in the algorithm is trivial: from the points {left, middle, right}, we choose the two with the minimal value of f. That is if f(left) < f(right), we chose [left, middle] and if f(left) > f(right), we choose [middle, right].

However, care should be taken that this algorithm is convergent for a minimization problem only in very special cases. A sufficient condition for the algorithm to converge (that is fortunately satisfied by the Euclidean distance) is that the function f is symmetrical with respect to its minimum in the interval we work with: f(x_min - d) = f(x_min + d), when x_min - d and x_min + d are inside the interval [a, b].

---

The second step now is to extend the above algorithm for a 3-dimensional minimization problem. Instead of the interval [a, b] we start with the initial cube (eight 3d points) and its center.

In the next step we choose the point among the eight corners that has the minimum f(x, y, z) - from that point and the center as diagonally opposite we form a new cube - that is we chose one of the eight "half-cubes" of the previous cube determined by the center.

The symmetry condition in this case can be written as f(x_min±dx, y_min±dy, z_min±dz) = f(x_min∓dx, y_min∓dy, z_min∓dz)

Here's the code for the continuous case (i.e., the coordinates are floating point numbers):

const x0 = Math.random()*100, y0 = Math.random()*100, z0 = Math.random()*100;
console.log('Original point', [x0, y0, z0]);

function dist(x, y, z){
     return Math.sqrt((x-x0)*(x-x0)+(y-y0)*(y-y0)+(z-z0)*(z-z0));
}

//utility function
function makeCube([xA, yA, zA], [xB, yB, zB]){
     return {
          cube:     [[xA, yA, zA],[xB, yA, zA],[xA, yB, zA],[xA, yA, zB],
               [xA, yB, zB], [xB, yB, zA], [xB, yA, zB], [xB, yB, zB]],
          center: [(xA+xB)/2, (yA+yB)/2, (zA+zB)/2]
     }
}

//utility function
function minIndex(a){
     return a.reduce(([minValue, minIndex], xi, i) => xi < minValue ? [xi, i] : [minValue, minIndex], [1/0, -1]);
}

function findPoint(eps = 1e-5, NMAX = 10000){
     let A = [0, 0, 0], B = [100, 100, 100];
     for(let i = 0; i < NMAX; i++){
          let {cube, center} = makeCube(A, B);
          const d = cube.map(p=>dist(...p));
          const [dMin, iMin] = minIndex(d);
          if(dMin < eps){
               return center;
          }
          A = cube[iMin];
          B = center;
     }
     
     return null; // failed after NMAX iterations
}

console.log('Found point', findPoint())

and its adaptation for the case the coordinates are integers

const x0 = Math.floor(Math.random()*101), y0 = Math.floor(Math.random()*101), z0 = Math.floor(Math.random()*101);
console.log('Original point', [x0, y0, z0]);

function dist(x, y, z){
     return Math.sqrt((x-x0)*(x-x0)+(y-y0)*(y-y0)+(z-z0)*(z-z0));
}

//utility function
function makeCube([xA, yA, zA], [xB, yB, zB]){
     return {
          cube:     [[xA, yA, zA],[xB, yA, zA],[xA, yB, zA],[xA, yA, zB],
               [xA, yB, zB], [xB, yB, zA], [xB, yA, zB], [xB, yB, zB]],
          center: [Math.round((xA+xB)/2), Math.round((yA+yB)/2), Math.round((zA+zB)/2)]
     }
}

//utility function
function minIndex(a){
     return a.reduce(([minValue, minIndex], xi, i) => xi < minValue ? [xi, i] : [minValue, minIndex], [1/0, -1]);
}

function findPoint(NMAX = 10000){
     let A = [0, 0, 0], B = [100, 100, 100];
     for(let i = 0; i < NMAX; i++){
          let {cube, center} = makeCube(A, B);
          const d = cube.map(p=>dist(...p));
          const [dMin, iMin] = minIndex(d);
          if(dMin === 0){
               console.log(i+' steps');
               return cube[iMin];
          }
          A = cube[iMin];
          B = center;
     }
     
     return null; // failed after NMAX iterations
}

console.log('Found point', findPoint())

Note that in both cases an optimization can be made by reusing the previously computed distance for the point in the new cube that was inherited from the previous cube, but I feel that it would make the code less readable.

---