We use cookies to improve your experience with our site.

一个优化的关于平面上最近点对问题的分治算法

An Optimized Divide-and-Conquer Algorithm for the Closest-Pair Problem in the Planar Case

  • 摘要: 我们给出了一种工程化的分治算法,该算法用来在给定的XY平面上的一组点中寻找最近点对。针对该算法,我们说明了对宽度为2δ的竖直板坯中的任一点,在组合步骤中只需要2次成对比较。论文证明了对于所有的p≥1情况下的Minkowski距离,算法的正确性。同时,我们经验性地说明了尽管该算法的时间复杂度仍然是O(n lg n),而当输入规模足够大时,对比的总次数的减少将会使得总的执行时间显著减少。

     

    Abstract: We present an engineered version of the divide-and-conquer algorithm for finding the closest pair of points, within a given set of points in the XY-plane. For this version of the algorithm we show that only two pairwise comparisons are required in the combine step, for each point that lies in the 2δ-wide vertical slab. The correctness of the algorithm is shown for all Minkowski distances with p ≥ 1. We also show empirically that, although the time complexity of the algorithm is still O(n lg n), the reduction in the total number of comparisons leads to a significant reduction in the total execution time, for inputs with size sufficiently large.

     

/

返回文章
返回