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?
[[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