最近点对算法

1.问题

在N个点中，寻找两个点使其距离最小。
如下为点的生成方式

2.解析

利用分治法，不断递归地将点集划分，如下x=m将图像划分为了左右两个子集。并最终求出左右两个子集的最短间距。并将该间距与分别存在于两个点子集中可能存在的比该间距更小的点对距离做比较，得解。

3.设计

最近点对算法

class Solve{

    private static double distance(Point p1, Point p2){ return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2)); }
    public static void preSort(Point[] PointArray){
        Arrays.sort(PointArray, new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return (o1.x > o2.x)?1:0;
            }
        });
    }

    static double solve(Point[] PointArray, int left, int right){
        double minDis = Double.MAX_VALUE;
        if(left == right)   return minDis;
        if(left + 1 == right)   return distance(PointArray[left], PointArray[right]);

        int middle = (left + right) / 2;
        double leftMinDis = solve(PointArray, left, middle);
        double rightMinDis = solve(PointArray, middle, right);

        minDis = Math.min(leftMinDis, rightMinDis);

        List<Integer> PINDEX = new ArrayList<>();
        for(int i = left; i <= right; i ++) if(Math.abs(PointArray[middle].x - PointArray[i].x) < minDis)   PINDEX.add(i);

        for (int i = 0; i < PINDEX.size(); i ++){
            for (int j = i  + 1; j < PINDEX.size(); j ++){
                if(Math.abs(PointArray[PINDEX.get(j)].y - PointArray[PINDEX.get(i)].y) > minDis) continue;

                double tempDis = distance(PointArray[PINDEX.get(i)], PointArray[PINDEX.get(j)]);

                minDis = Math.min(tempDis, minDis);
            }
        }

        return minDis;
    }
}

4.分析

O(n) =nlogn

5.源码

https://github.com/JessySnow/Algorithm/blob/master/src/T5/Distance.java