1
\$\begingroup\$

I have tried to calculate the minimum distance between the two points in a 2D plane. I have used the divide and conquer strategy to attain the complexity of n logn. The steps that I did are:

  • Recursively sort a list in X plane and compute the minimum difference between the coordinates sorted by X plane.
  • Recursively sort a list in Y plane compute the minimum difference between the coordinates sorted by Y plane.
  • Compute the min of the two from the above steps
  • It will be the result

Here is my code:

var points = [
  [1, 6],
  [1, 1],
  [2, 1],
  [1.5, 1]
];

var smallestDifference;

function mergeSort(arr, dimension = 'x') {
  if (arr.length == 1)
    return arr;

  if (arr.length > 1) {
    let breakpoint = Math.ceil((arr.length / 2));
    // Left list starts with 0, breakpoint-1
    let leftList = arr.slice(0, breakpoint);
    // Right list starts with breakpoint, length-1
    let rightList = arr.slice(breakpoint, arr.length);

    // Make a recursive call
    leftList = mergeSort(leftList, dimension);
    rightList = mergeSort(rightList, dimension);

    var a = merge(leftList, rightList, dimension);
    return a;
  }
}

function merge(leftList, rightList, dimension) {
  let result = [];
  let dimensionIndex;
  if ('x' == dimension) {
    dimensionIndex = 0;
  } else if ('y' == dimension) {
    dimensionIndex = 1;
  }
  while (leftList.length && rightList.length) {
    // Sorting the x/y coordinates
    if (leftList[0][dimensionIndex] <= rightList[0][dimensionIndex]) {
      result.push(leftList.shift());
    } else {
      result.push(rightList.shift());
    }
  }

  while (leftList.length)
    result.push(leftList.shift());

  while (rightList.length)
    result.push(rightList.shift());

  // Compute the distance using the distance formula
  let difference = Math.sqrt(Math.pow(result[1][0] - result[0][0], 2) + Math.pow(result[1][1] - result[0][1], 2));
  if (smallestDifference) {
    if (difference < smallestDifference)
      smallestDifference = difference;
  } else {
    smallestDifference = difference;
  }
  return result;
}

var resultX = mergeSort(points, 'x');
var resultY = mergeSort(points, 'y');

document.write(`Minimum distance between two points: ${smallestDifference}`);

With the inputs that I have tried, I have found the results to be correct. But is this the good/best way to approach this? If this solution were to be improved what changes would be made?

\$\endgroup\$
  • \$\begingroup\$ Your algorithm fails at [[1, 1], [1, 2], [1, 4], [1, 4.5], [2, 5]]. However, your intuition that there is a \$\Theta(n \log n)\$ algorithm is correct. \$\endgroup\$ – coderodde Mar 28 '17 at 16:02
  • \$\begingroup\$ Do you mean find the distance between the two closest points? Your title and summary seem confusing since you are dealing with more than two points as input. \$\endgroup\$ – Mike Brant Mar 28 '17 at 16:42
  • \$\begingroup\$ @MikeBrant Yes, I mean the distance. \$\endgroup\$ – Suhail Gupta Mar 29 '17 at 3:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.