平面点集最近点对分治算法的改进

"本文主要讨论了对平面点集最近点对问题的一种改进算法，该算法源于Preparata和Shamos在1985年的原始分治策略，旨在降低计算复杂度，提高算法效率。" 在计算机科学中，尤其是在算法设计与分析领域，寻找平面点集中的最近点对是一个经典的问题。这个问题的基本目标是在一组给定的二维平面上的点中，找到距离最近的两个点。Preparata和Shamos在1985年提出了一种基于分治策略的算法来解决这个问题，但其原始版本在归并阶段需要计算最多3n对点对的距离，时间复杂度为3nlogn。 本文的作者周玉林、熊鹏荣和朱洪对这一算法进行了改进。他们通过优化分治过程，将归并过程中计算距离的对数从3n降低到了2n。这意味着在最坏情况下，改进后的算法所需计算的距离数量减少了一半，时间复杂度相应地降低到了2nlogn。这是一个显著的优化，因为在处理大规模数据集时，这样的减少可以极大地提升算法的运行速度和效率。 分治算法是一种常见的问题解决策略，它将大问题分解成小问题来解决，然后合并这些小问题的解来获得原问题的解。在最近点对问题中，分治算法通常涉及将点集分成两半，分别计算每半内的最近点对，然后处理两半之间的边界情况，以找到全局最近的点对。 改进的算法可能包括更精细的点对比较和筛选机制，减少了不必要的距离计算。这可能是通过更有效的数据结构，如平衡二叉搜索树或kd树，或者通过改进的边界处理技术实现的。然而，具体的技术细节未在摘要中给出，需要查阅完整的论文才能获取详细信息。 这个改进对于计算几何、数据结构和算法设计等领域具有重要意义，因为它提供了一个更高效的解决方案，可以用于处理大规模数据集，特别是在空间索引、地理信息系统和多边形碰撞检测等应用中。 关键词: 分治算法、最近点对、算法复杂性、计算机科学、二维几何、效率优化 中图法分类号: TP30116（计算机科学技术）