Java中如何利用几何数据结构解决最近点对问题？

　　1、问题描述： 最近点对问题是指在给定的点集中找到距离最近的一对点。

　　2、分治策略： 通过分治法将点集分为两个子集，分别求解子集的最近点对，再在子集间找最近点对。

　　3、边界处理： 考虑边界附近的点对可能跨越两个子集，需在分割线的两侧设定宽度的条带进行检查。

　　4、距离比较： 在条带内按y坐标排序点，只在垂直距离小于当前最近距离的点对间进行距离比较。

　　5、复杂度优化： 结合分治和条带内的局部检查可以将复杂度优化到O(n log n)。

很赞哦！

python编程网提示：转载请注明来源www.python66.com。
有宝贵意见可添加站长微信(底部)，获取技术资料请到公众号(底部)。同行交流请加群