1 introduction

This blog post is arranged according to the homework of the algorithm experiment class, and the implementation code is Java. If there is any loose or wrong place, please point out in the comments section.

2 Problem Description

Problem description: There are n points on a two-dimensional plane, how to find the nearest point?

3 partition method

Divide-and-conquer method: decompose a larger problem into smaller sub-problems, solve these sub-problems first, and then combine the solutions of each sub-problem to obtain the solution of the original problem.

Recursion: Directly or indirectly calling its own methods. Recursion is usually a divide-and-conquer solution.

  • Disadvantages of recursion: the specific execution steps are complicated to understand;
  • Recursion advantage: easy to implement, the general idea is clear.

4 Solving violence

4.1 Algorithm Thinking

If there are n points on the two-dimensional plane, then (n-1)+(n-1)+… +1=n(n-1)/2 point pairs, and you can iterate over them to find the distance between all of them.

4.2 Time complexity Analysis

According to 4.1 analysis, n(n-1)/2 distances are required in total, so the time complexity is O(n^2).

4.3 Code Implementation

public static double getByBruteFoce(double[][] points) { int head=0; int tail=points.length-1; double minDist=getDistance(points,head,head+1); Int [] minIndex=new int[] {head,head+1}; For (int I =head; i<=tail-1; For (int j= I +1; j<=tail; j++) { if(getDistance(points,i,j)<minDist) { minDist=getDistance(points,i,j); // minIndex[0]= I; MinIndex [1]=j; } } } return minDist; }Copy the code

5. Divide and conquer

5.1 Algorithm Ideas

Core ideas:

  1. Data preprocessing
  2. Dividing central axis
  3. Find the minimum distance on the left
  4. Find the minimum distance on the right half
  5. Find the minimum distance between them
  6. Compare these three minimum distances

Step 1: Data preprocessing

Because the positions of these points are randomly generated and stored in a two-dimensional array, we first have to sort these points in order of x, from smallest to largest, and adjust their order in the two-dimensional array. For example, the leftmost point is stored in the first element of the two-dimensional array.

Step 2: Divide the central axis

Divide these points on the plane into left and right sides.

On what basis to divide the central axis?

Take the two middle elements, find the average of their x-coordinates, and set it to the coordinates of the central axis.

Step 3: find the minimum half distance

The way to minimize the distance between the left and right sides is the same. If we’re dealing with the left side, let’s think of the left side as a whole, and let’s divide it into the left and the right, recursively, getting smaller and smaller.

When does recursion stop?

It stops when there are only a small number of points left, such as when there are only four points left on the plane in the additional code in this article.

Step 4: Find the minimum distance between them

How wide should the middle area be?

We only need to examine the points on the left and right sides of the central axis that are less than d. Reason: distance from the axis of those points greater than D, they and the other half of the point distance, must be greater than D, examine them there is no meaning.So now we just need to compare the two points on the left and the four points on the right.

How to further optimize?

So let’s say we pick m on the left, but actually, we don’t have to compare it to all four points on the right, we just have to compare it to the points that are within d of the shaded part on the right, that is, the two points that are perpendicular to m. If the vertical distance between two points is greater than D, then the distance between the two points must be greater than D.

A further note on rectangles

If you’ve looked at other sources, you’ve probably heard that we can only have six points in a DX2D region. Because we know that the minimum distance between the two sides is D, and the points in dx2D are on the same side. So the distance between these points has to be greater than or equal to d, and with some geometry, we can figure out that there are at most six points in this region.

5.2 Code Implementation

5.2.1 Data preprocessing

In this case, I used a more efficient quicksort algorithm.

// Data processing: Private static double[][] quickSort(double[][] oldData) {double[][] newData= olddata.clone (); private static double[][] quickSort(double[][] oldData) {double[][] newData=oldData. QSRecursion(newData,0,newData.length-1); return newData; } private static void QSRecursion(double[][] newData, int i, int j) { if(i==j)return; int standardIndex=i+new java.util.Random().nextInt(j-i+1); int pivot=partition(newData,i,j,standardIndex); // Save the correct position of the base element if(pivot! =i)QSRecursion(newData,i,pivot-1); / / on the left side of the if (pivot! =j)QSRecursion(newData,pivot+1,j); Private static int partition(double[][] newData, int I, int j, int standardIndex) { swap(newData,i,standardIndex); Int left= I +1; Int right=j; While (newData[left][0]<=newData[I][0]&left<right) {left++; } while(newData[right][0]>=newData[i][0]&left<right) { right--; } if(left<right) { swap(newData,right,left); }} if(newData[right][0]>newData[I][0]) {swap(newData,right-1, I); standardIndex=right-1; }else { swap(newData,j,i); standardIndex=j; } return standardIndex; } private static void swap(double[][] newData, int a, int b) {double[] temp=newData[a]; newData[a]=newData[b]; newData[b]=temp; }Copy the code

5.2.2 partition method

/ / partition method to solve the public static double getByDivideConquer (double [] [] points) {if (points. The length = = 1 | points. The length = = 0) {return 0; } double[][] pointsSorted=quickSort(points); // for(int i=0; i<pointsSorted.length; I++) / / check if ordering right / / {/ / System. Out. Println (pointsSorted [I] [0]). // // } int head=0; int tail=pointsSorted.length-1; int [] minIndex=getByDivideConquer(pointsSorted,head,tail); double minDist=getDistance(pointsSorted,minIndex[0],minIndex[1]); return minDist; } ///////////////////////////////////////////// private static int[] getByDivideConquer(double[][] points, int head, int tail) { double minDist=getDistance(points,head,head+1); Int [] minIndex=new int[] {head,head+1}; If (tail-head+1<=4) {for(int I =head; i<=tail-1; For (int j= I +1; j<=tail; j++) { if(getDistance(points,i,j)<minDist) { minDist=getDistance(points,i,j); minIndex[0]=i; minIndex[1]=j; } } } }else { int [] minIndexLeft=getByDivideConquer(points,head,head+(tail-head)/2); int [] minIndexRight=getByDivideConquer(points,head+(tail-head)/2+1,tail); double minDisLeft=getDistance(points,minIndexLeft[0],minIndexLeft[1]); double minDisRight=getDistance(points,minIndexRight[0],minIndexRight[1]); double minDisTwoSide=Math.min(minDisLeft, minDisRight); If (minDisLeft>=minDisRight) {dist =minDisRight; minIndex=minIndexRight; }else { minDist=minDisLeft; minIndex=minIndexLeft; } double middleAxis=(points[head+(tail-head)/2][0]+points[head+(tail-head)/2+1][0])/2; Int I =head+(tail-head)/2+1; While (I <=tail&&(points[I][0] -middleaxis <minDisTwoSide) {int count=0; for(int j=head+(tail-head)/2; j>=head&&(points[j][0]-middleAxis<minDisTwoSide)&&(count<=6); Math.abs(points[j][1]-points[j][1])<minDisTwoSide) {math.abs (points[j][1])<minDisTwoSide) {math.abs (points[j][1])<minDisTwoSide) if(getDistance(points,i,j)<minDist) { minDist=getDistance(points,i,j); minIndex[0]=i; minIndex[1]=j; } count++; } } i++; } } } return minIndex ; } / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / / the distance calculation points I and j private static double getDistance (double [] [] points, int i, int j) { double dis=Math.sqrt(Math.pow(points[i][0]-points[j][0], 2)+Math.pow(points[i][1]-points[j][1], 2)); //System.out.println(dis); // Test output return dis; }Copy the code