# Compute the minimum distance between two points in a 2-D plane

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?

• 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. – coderodde Mar 28 '17 at 16:02
• 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. – Mike Brant Mar 28 '17 at 16:42
• @MikeBrant Yes, I mean the distance. – Suhail Gupta Mar 29 '17 at 3:17